本地、ide和测试机答案均不一致
查看原帖
本地、ide和测试机答案均不一致
775213
yangmingshuo114514楼主2024/8/16 23:57

我的代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,i,a,j,b;
int c[20000005];
int edge_tot,h[20000005],to[20000005],nxt[20000005];
int dfn_tot,dfn[20000005],low[0000005];
int stk[20000005],idx,col[20000005];
bool vis[20000005];
int bl_tot;
void add_edge(int x,int y){
	to[++edge_tot]=y;
	nxt[edge_tot]=h[x];
	h[x]=edge_tot;
}
void tarjan(int x){
	dfn[x]=low[x]=++dfn_tot;
	stk[++idx]=x;
	vis[x]=1;
    for(int i=h[x];i;i=nxt[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        bl_tot++;
        while(stk[idx]!=x){
            col[stk[idx]]=bl_tot;
            vis[stk[idx]]=0;
            --idx;
        }
        col[stk[idx]]=bl_tot;
        vis[stk[idx]]=0;
        --idx;
    }
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d%d%d",&i,&a,&j,&b);
        if(a==0&&b==0){
            add_edge(i+n,j);
            add_edge(j+n,i);
        }
        if(a==0&&b==1){
            add_edge(i+n,j+n); 
            add_edge(j,i);
        }
        if(a==1&&b==0){
            add_edge(i,j); 
            add_edge(j+n,i+n); 
        }
        if(a==1&&b==1){
            add_edge(i,j+n); 
            add_edge(j,i+n); 
        }
	}
	for(int i=1;i<=2*n;i++)
		if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++)
		if(col[i]==col[i+n]){
			printf("IMPOSSIBLE");
			return 0;
		}
	printf("POSSIBLE\n");
	for(int i=1;i<=n;i++)
		printf("%d",col[i]>col[i+n]),putchar(' ');
	return 0;
}

输入:

10 10
3 0 2 0
10 1 9 0
2 1 4 0
10 1 2 1
2 1 2 0
10 1 9 1
2 1 4 0
10 0 9 1
1 1 8 1
8 0 2 1

本地输出:

POSSIBLE
0 0 1 0 0 0 0 1 1 1

ide:

POSSIBLE
0 1 0 0 0 0 0 1 0 0

然后评测机说:

Wrong Answer.wrong answer Wrong in No.2 clause , input is {10,1,9,0} , your xval is 0 , yval is 1

求问这是怎么回事?

2024/8/16 23:57
加载中...