为什么没过样例还AC了
查看原帖
为什么没过样例还AC了
942220
cyyzliangyuhan楼主2025/7/20 08:30

有没有巨佬帮忙看看为什么样例没过,但是AC了

#include<bits/stdc++.h>
using namespace std;
const int N=8e6+10;
int n,tot,tr[N][2],cnt,step,low[N],dfn[N],col[N]; 
string s[N]; 
vector<int> g[N];
stack<int> st;
bool vis[N];
void tarjan(int x){
	dfn[x]=++step; low[x]=dfn[x];
	st.push(x); vis[x]=1;
	for(int v:g[x]){
		if(!dfn[v]){
			tarjan(v); low[x]=min(low[x],low[v]);
		}else if(vis[v]) low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x]){
		++cnt; int y;
		do{
			y=st.top(); st.pop();
			col[y]=cnt; vis[y]=0;
		}while(y!=x);
	}
}
void dfs(int x){
	if(tr[x][0]) dfs(tr[x][0]);
	if(tr[x][1]) dfs(tr[x][1]);
	bool flag=0;
	for(int i=0;i<g[x-2].size();i++){
		int v=g[x-2][i];
		if(v==x) continue;
		if(flag){
			if(v>n) g[v-n].push_back(tot-1);
			else g[v+n].push_back(tot-1);
			g[tot].push_back(v);
		}
		g[++tot].push_back(v);
		if(v>n) g[v-n].push_back(++tot);
		else g[v+n].push_back(++tot);
		if(flag){
			g[tot-1].push_back(tot-3);
			g[tot-2].push_back(tot);
		}
		flag=1;
	}
	flag=0;
	for(int i=g[x-2].size()-1;i>=0;i--){
		int v=g[x-2][i];
		if(v==x) continue;
		if(flag){
			if(v>n) g[v-n].push_back(tot-1);
			else g[v+n].push_back(tot-1);
			g[tot].push_back(v);
		}
		g[++tot].push_back(v);
		if(v>n) g[v-n].push_back(++tot);
		else g[v+n].push_back(++tot);
		if(flag){
			g[tot-1].push_back(tot-3);
			g[tot-2].push_back(tot);
		}
		flag=1;
	}
}
void ins(int x,int op){
	int p=2*n+3;
	for(int i=0;i<s[x].size();i++){
		int c=s[x][i];
		if(c!='0'&&c!='1') c=op;
		else c=c-'0';
		if(!tr[p][c]){
			tr[p][c]=tot+3;
		    g[p].push_back(++tot);
		    g[++tot].push_back(p+1);
		    g[tot-1].push_back(++tot);
		    g[++tot].push_back(tot-2);
		}
		p=tr[p][c];
	}
	g[x+op*n].push_back(p);
	g[p+1].push_back(x+(op^1)*n);
	g[p-2].push_back(x+(op^1)*n);
	g[x+op*n].push_back(p-1);
}
int main(){
	scanf("%d",&n); tot=2*n+4;
	g[2*n+1].push_back(2*n+3);
	g[2*n+4].push_back(2*n+2);
	for(int i=1;i<=n;i++){
		cin>>s[i]; ins(i,0); ins(i,1);
	}
	dfs(2*n+3); 
	for(int i=1;i<=tot;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=n;i++){
		if(col[i]==col[i+n]){
			cout<<"NO"<<"\n";
			return 0;
		}
	}
	for(int i=n*2+1;i<tot;i+=2){
		if(col[i]==col[i+1]){
			cout<<"NO"<<"\n";
			return 0;
		}
	}
	cout<<"YES"<<"\n";
	for(int i=1;i<=n;i++){
		for(int j=0;j<s[i].size();j++){
			if(s[i][j]=='?') cout<<(col[i]>col[i+n]);
			else cout<<s[i][j];
		}
		cout<<"\n";
	} 
	return 0;
}

输出

YES
000
0100
01
100
2025/7/20 08:30
加载中...