結果

問題 No.1553 Lovely City
ユーザー tails
提出日時 2021-06-18 23:10:27
言語 cLay
(20241019-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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

{
	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]);
	}
}
0