#668032 (cLay) No.1553 Lovely City

• 問題: No.1553 Lovely City
• ユーザー: tails
• 提出日時: 2021-06-18 23:10:27
• 言語: cLay (20240714-1)
• 結果: WA
• 実行時間: -
• コード長: 941 bytes
• コンパイル時間: 3,349 ms
• コンパイル使用メモリ: 193,556 KB
• 実行使用メモリ: 23,012 KB
• 最終ジャッジ日時: 2024-07-05 15:17:56
• 合計ジャッジ時間: 9,331 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	27 ms; 22,016 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	50 ms; 22,668 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	40 ms; 19,156 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]);
	}
}