WA on #10
查看原帖
WA on #10
965341
jcls楼主2023/11/28 18:49

洛谷数据100,官方数据90,第10个点的第2个第4个错了。求助。代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct xx{
    int x,c;
}fx,fy,f[N];
int c,t,i,n,m,x,y,ans,p[N],fa[N],co[N];
char op;
char read(){
    char ch=getchar();
    while(ch!='T'&&ch!='F'&&ch!='U'&&ch!='+'&&ch!='-')ch=getchar();
    return ch;
}
xx find(int x){
    if(f[x].x==x)return f[x];
    xx y=find(f[x].x);
    f[x].x=y.x;f[x].c^=y.c;
    return f[x];
}
int main(){
    scanf("%d%d",&c,&t);
    while(t--){
        ans=0;memset(p,0,sizeof(p));memset(co,0,sizeof(co));memset(f,0,sizeof(f));
        scanf("%d%d",&n,&m);
        for(i=1;i<=n+3;i++)fa[i]=i,f[i].x=i;
        for(i=1;i<=m;i++){
            op=read();
            if(op=='T'){
                scanf("%d",&x);
                fa[x]=n+1;co[i]=0;
            }else if(op=='F'){
                scanf("%d",&x);
                fa[x]=n+3;co[x]=0;
            }else if(op=='U'){
                scanf("%d",&x);
                fa[x]=n+2;co[x]=0;
            }else if(op=='+'){
                scanf("%d%d",&x,&y);
                fa[x]=fa[y];co[x]=co[y];
            }else{
                scanf("%d%d",&x,&y);
                fa[x]=fa[y];co[x]=1-co[y];
            }
        }
        for(i=1;i<=n;i++){
            fx=find(i);fy=find(fa[i]);
            f[fx.x].x=fy.x;f[fx.x].c^=fy.c^co[i];
        }
        for(i=1;i<=n;i++)f[i]=find(f[i].x);
        for(i=1;i<=n;i++)
            if(f[i].x==n+2||f[i].x==i&&f[i].c)p[i]=1;
        for(i=1;i<=n;i++)
            if(f[i].x<=n)p[i]=p[f[i].x];
        for(i=1;i<=n;i++)ans+=p[i];
        printf("%d\n",ans);
    }
	return 0;
}
2023/11/28 18:49
加载中...