#668032 (cLay) No.1553 Lovely City

• 問題: No.1553 Lovely City
• ユーザー: tails
• 提出日時: 2021-06-18 23:10:27
• 言語: cLay (20240104-1)
• 結果: WA
• 実行時間: -
• コード長: 941 bytes
• コンパイル時間: 3,213 ms
• コンパイル使用メモリ: 192,084 KB
• 実行使用メモリ: 25,604 KB
• 最終ジャッジ日時: 2023-09-19 02:28:25
• 合計ジャッジ時間: 10,162 ms
• ジャッジサーバーID （参考情報）: judge14 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	27 ms; 22,608 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	56 ms; 25,604 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	47 ms; 21,820 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-

ソースコード

{
	VI resu,resv;

	graph g;
	int @n,@m;
	VI u(m),v(m);
	rd((u,v)(m));
	g.setDirectEdge(n+1,m,u.data(),v.data());
	VI ss(n+1);
	int sn=g.scc(ss.data());
	if(sn==n+1){
		VI resu,resv;
		VI rev(sn);
		rep(i,sn) rev[ss[i]]=i;
		unionFind uf;
		uf.walloc(sn,1);
		rep(i,m){
			int su=ss[u[i]];
			int sv=ss[v[i]];
			if(su!=sv){
				uf(su,sv);
			}
		}
		vector<VI> vv(sn);
		rep(i,sn){
			vv[uf(i)].push_back(i);
		}
		rep(i,sn){
			int n=vv[i].size();
			if(n>1){
				sort(vv[i].begin(),vv[i].end());
				rep(j,n-1){
					resu.push_back(rev[vv[i][j]]);
					resv.push_back(rev[vv[i][j+1]]);
				}
			}
		}
		int rn=resu.size();
		wt(rn);
		rep(i,rn){
			wt(resu[i],resv[i]);
		}
	}else{
		// wakka
		VI res;
		VI saw(n+1);
		rep(i,m){
			if(!saw[u[i]]++){
				res.push_back(u[i]);
			}
			if(!saw[v[i]]++){
				res.push_back(v[i]);
			}
		}
		int rn=res.size();
		wt(rn);
		rep(i,rn-1){
			wt(res[i],res[i+1]);
		}
		wt(res[rn-1],res[0]);
	}
}