#686969 (C++14) No.1640 簡単な色塗り

提出ソース

結果

問題	No.1640 簡単な色塗り
ユーザー	tpc011854
提出日時	2021-08-06 23:16:52
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	2,560 bytes
コンパイル時間	494 ms
コンパイル使用メモリ	50,192 KB
実行使用メモリ	37,532 KB
最終ジャッジ日時	2023-09-12 03:14:50
合計ジャッジ時間	13,051 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 25,588 KB
testcase_01	AC	8 ms 25,520 KB
testcase_02	AC	8 ms 29,596 KB
testcase_03	AC	8 ms 25,572 KB
testcase_04	AC	36 ms 25,940 KB
testcase_05	AC	53 ms 34,736 KB
testcase_06	AC	8 ms 29,596 KB
testcase_07	AC	8 ms 29,600 KB
testcase_08	AC	9 ms 29,648 KB
testcase_09	AC	8 ms 25,440 KB
testcase_10	AC	179 ms 29,312 KB
testcase_11	AC	104 ms 29,000 KB
testcase_12	AC	151 ms 30,796 KB
testcase_13	AC	484 ms 30,348 KB
testcase_14	AC	516 ms 31,956 KB
testcase_15	AC	54 ms 28,492 KB
testcase_16	AC	315 ms 28,732 KB
testcase_17	AC	395 ms 29,876 KB
testcase_18	AC	16 ms 29,872 KB
testcase_19	AC	87 ms 28,896 KB
testcase_20	AC	188 ms 29,292 KB
testcase_21	AC	161 ms 29,040 KB
testcase_22	AC	11 ms 29,780 KB
testcase_23	AC	127 ms 29,412 KB
testcase_24	AC	37 ms 30,152 KB
testcase_25	AC	175 ms 28,908 KB
testcase_26	AC	189 ms 29,644 KB
testcase_27	AC	55 ms 28,444 KB
testcase_28	AC	507 ms 30,168 KB
testcase_29	AC	235 ms 29,684 KB
testcase_30	AC	14 ms 30,320 KB
testcase_31	AC	70 ms 32,364 KB
testcase_32	AC	55 ms 34,392 KB
testcase_33	AC	42 ms 30,860 KB
testcase_34	AC	47 ms 33,852 KB
testcase_35	AC	39 ms 32,740 KB
testcase_36	AC	15 ms 30,328 KB
testcase_37	AC	18 ms 30,780 KB
testcase_38	AC	58 ms 32,068 KB
testcase_39	AC	29 ms 31,480 KB
testcase_40	AC	27 ms 31,300 KB
testcase_41	AC	52 ms 31,388 KB
testcase_42	AC	33 ms 29,620 KB
testcase_43	AC	33 ms 30,032 KB
testcase_44	AC	31 ms 31,932 KB
testcase_45	AC	26 ms 31,540 KB
testcase_46	AC	16 ms 30,488 KB
testcase_47	AC	12 ms 30,232 KB
testcase_48	AC	64 ms 34,908 KB
testcase_49	AC	11 ms 29,780 KB
testcase_50	AC	7 ms 25,384 KB
testcase_51	AC	8 ms 25,548 KB
testcase_52	AC	99 ms 37,532 KB
testcase_53	WA	-
07_evil_01.txt	WA	-
07_evil_02.txt	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cstdio>
#include <vector>
using std::vector;
int a[500005], b[500005];
struct Edge {
	int u, v;
	int id;
};
vector<Edge> g[500005];
int color[500005];
int cnt[500005];
int vis[500005];
Edge c[500005];
int stack[500005]; int top = 0;
int usedEdge[500005]; int tt = 0;
int set[500005];
int all[500005];

void dfs(int u){
	//printf("u = %d\n",u);
	stack[++top] = u;
	vis[u] = 1;
	for(Edge e: g[u]){
		int v = e.v;
		if(!color[e.id] && !vis[v]){
			usedEdge[++tt] = e.id;
			color[e.id] = v;
			dfs(v);
		}
	}
}

void dfs1(int u){
	//printf("uu = %d\n",u);
	vis[u] = 1;
	set[u] = 1;
	for(Edge e: g[u]){
		int v = e.v, id = e.id;
		//printf("v = %d\n",v);
		if(!color[id] && !vis[v]){
			color[id] = v;
			dfs1(v);
		}
	}
}

int main(){
	//printf("haha\n");
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		scanf("%d%d",&a[i],&b[i]);
		cnt[a[i]]++;
		cnt[b[i]]++;
	} 
	for(int i = 1; i <= n; i++){
		if(cnt[a[i]]==1){
			color[i] = a[i];
			vis[a[i]] = 1;
			//dfs1(a[i]);
		}
		else if(cnt[b[i]]==1){
			color[i] = b[i];
			vis[b[i]] = 1;
			//dfs1(a[i]);
		}
		else if(a[i]==b[i]){
			color[i] = b[i];
			vis[b[i]] = 1;
			//dfs1(a[i]);
		}
		else{
			g[a[i]].push_back(Edge{a[i], b[i],i});
			g[b[i]].push_back(Edge{b[i], a[i],i});
		}
	}
	//printf("ok\n");
	for(int i = 1; i <= n; i++) if(vis[i] && !set[i]) dfs1(i);
	//printf("break\n");
	for(int i = 1; i <= n; i++){
		if(!vis[i]){
			//printf("i = %d\n",i);
			int find = -1;
			int u = i;
			for(Edge e: g[u]){
				if(!color[e.id]){
					find = e.id;
					break;
				}
			}
			if(find==-1){
				break;
			}
			else{
				top = 0;
				tt = 0;
				//printf("find = %d: %d %d\n",find,a[find],b[find]);
				color[find] = a[find];
				dfs(a[find]);
				int bad = !vis[b[find]];
				//printf("vis[%d] = %d\n",b[find],vis[b[find]]);
				for(int j = 1; j <= top; j++) vis[stack[j]] = 0;
				for(int j = 1; j <= tt; j++) color[usedEdge[j]] = 0;
				if(bad){
					top = 0;
					//printf("haha\n");
					color[find] = b[find];
					dfs(b[find]);
					int bb = !vis[a[find]];
					for(int j = 1; j <= top; j++) vis[stack[j]] = 0;
					for(int j = 1; j <= tt; j++) color[usedEdge[j]] = 0;
					//if(bb) break;
					//else{ 
						dfs1(b[find]);
					//}
				}
				else dfs1(a[find]);
			}
		}
	}
	int find = 0;
	for(int i = 1; i <= n; i++){ 
		if(!vis[i]) find = 1;
	}
	if(find) printf("No\n");
	else{
		printf("Yes\n");
		for(int i = 1; i <= n; i++) printf("%d\n",color[i]);
		//for(int i = 1; i <= n; i++) all[color[i]]++;
		//for(int i = 1; i <= n; i++) if(all[i]!=1) printf("-1\n");
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード