CODEVS 2456 奇偶游戏

带权并查集

题目传送门

感觉和数石子差不多，把值改为奇偶即可。

注意特判所有问题都符合的情况。

代码：

#include
#include
#include
#define MAXN 5000
using namespace std;
int n,l,node;
int fa[MAXN+5],que[MAXN+5][2],px[2*MAXN+5];
bool f[MAXN+5];
int dis[MAXN+5];
int calc(int x){int l=1,r=node;while (l<=r){int mid=px[(l+r)/2];if (mid==x) return (l+r)/2;if (mid2+1;else r=(l+r)/2-1;}
}
int findfather(int x){if (fa[x]==x) return x;int fx=findfather(fa[x]);(dis[x]+=dis[fa[x]])&=1;return fa[x]=fx;
}
int main(){scanf("%d%d",&l,&n);memset(f,false,sizeof(f));memset(dis,0,sizeof(dis));for (int i=1;i<=n;i++){char s[10];scanf("%d%d%s",&que[i][0],&que[i][1],s);que[i][0]--;if (s[0]=='o')f[i]=true;}for (int i=1;i<=n;i++){px[++node]=que[i][1];px[++node]=que[i][0];}sort(px+1,px+node+1);node=unique(px+1,px+node+1)-px-1;for (int i=1;i<=node;i++)fa[i]=i;for (int i=1;i<=n;i++){int x=calc(que[i][0]),y=calc(que[i][1]);int fx=findfather(x),fy=findfather(y);if (fx!=fy){fa[fy]=fx;(dis[fy]=f[i]-dis[y]+dis[x]+2)&=1;}elseif ((dis[y]-dis[x]+2&1)!=f[i]){printf("%d\n",i-1);return 0;}}printf("%d\n",n);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！