tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

2011 Shiritori

今いる頂点の強連結成分に入ってくる辺がなくなるまで同じ強連結成分で単語を回していって、なくなったら次の強連結成分にすすめていくだけ。
O(V^2)の強連結成分分解をO(V^2)回繰り返すこととO(E)回次どこに進めるかO(V)で調べるのでO(V^4+EV)になります。間に合います。
ちなみに強連結成分分解のときの初期化のミスと「今いる頂点の強連結成分に入ってくる辺がなくなる」判定を間違えていたので4WAもしていました。最近事故りまくっていてよくない。本番に強ければいいですね。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int mat[100][100];
int now[100][100];
vector<long long>g[100][100];
int rev[100][100];
int in[100];
int out[100];
int num[100];
int v[100];
int SCC[100];
int SIZ[100];
int s;
void dfs(int a){
	v[a]=1;
	for(int i=0;i<100;i++){
		if(!~v[i]&&mat[a][i]!=now[a][i]){
			dfs(i);
		}
	}
	num[s++]=a;
}
void dfs2(int a){
	SCC[a]=s;
	SIZ[s]++;
	for(int i=0;i<100;i++){
		if(!~SCC[i]&&rev[a][i])dfs2(i);
	}
}
void scc(){
	s=0;
	for(int i=0;i<100;i++)v[i]=num[i]=SCC[i]=-1;
	for(int i=0;i<100;i++){
		SIZ[i]=0;
		for(int j=0;j<100;j++){
			rev[i][j]=0;
		}
	}
	for(int i=0;i<100;i++)
		for(int j=0;j<100;j++)
			if(mat[i][j]!=now[i][j])rev[j][i]=1;
	for(int i=0;i<100;i++){
		if(!~v[i])dfs(i);
	}
	s=0;
	for(int i=99;i>=0;i--){
		if(!~SCC[num[i]]){
			dfs2(num[i]);
			s++;
		}
	}
}
int UF[100];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);
	b=FIND(b);
	if(a==b)return;
	UF[a]+=UF[b];
	UF[b]=a;
}
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<100;i++)UF[i]=-1;
	for(int i=0;i<a;i++){
		long long b;
		scanf("%lld",&b);
		mat[b/100000000][b%100]++;
		g[b/100000000][b%100].push_back(b);
		in[b%100]++;
		out[b/100000000]++;
		UNION(b/100000000,b%100);
	}
	for(int i=0;i<100;i++)
		for(int j=0;j<100;j++)
			std::sort(g[i][j].begin(),g[i][j].end());
	bool ok=true;
	int C1=0;
	int C2=0;
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			if(FIND(i)!=FIND(j)&&in[i]+out[i]&&in[j]+out[j]){
				ok=false;
			}
		}
		if(in[i]+1<out[i])ok=false;
		if(out[i]+1<in[i])ok=false;
		if(in[i]+1==out[i])C1++;
		if(out[i]+1==in[i])C2++;
	}
	if(C1>1||C2>1)ok=false;
	if(!ok){
		printf("impossible\n");
		return 0;
	}
	int at=0;
	if(C1==0){
		for(int i=0;i<100;i++)
			if(out[i]){
				at=i;
				break;
			}
	}else{
		for(int i=0;i<100;i++)
			if(out[i]>in[i]){
				at=i;
				break;
			}
	}
	
	for(int i=0;i<a;i++){
	//	printf("%d\n",at);
		long long MIN=19999999999LL;
		for(int j=0;j<100;j++){
			if(mat[at][j]!=now[at][j]){
			//	printf("%d %d ",SCC[at],SCC[j]);
			//	printf("%d\n",SIZ[SCC[at]]);
				if(in[at]==0){
					MIN=min(MIN,g[at][j][now[at][j]]);
				}else{
					if(SCC[at]==SCC[j]){
						MIN=min(MIN,g[at][j][now[at][j]]);
					}
				}
			}
		}
		printf("%010lld\n",MIN);
		now[at][MIN%100]++;
		if(mat[at][MIN%100]==now[at][MIN%100])scc();
		at=MIN%100;
		in[at]--;
	}
}