結果

問題 No.1553 Lovely City
ユーザー hongrockhongrock
提出日時 2021-06-20 18:39:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,450 bytes
コンパイル時間 1,836 ms
コンパイル使用メモリ 177,840 KB
実行使用メモリ 36,648 KB
最終ジャッジ日時 2024-06-22 22:34:06
合計ジャッジ時間 10,043 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
19,968 KB
testcase_01 AC 6 ms
20,096 KB
testcase_02 AC 45 ms
34,980 KB
testcase_03 AC 9 ms
20,096 KB
testcase_04 AC 9 ms
20,224 KB
testcase_05 AC 7 ms
20,224 KB
testcase_06 AC 7 ms
20,224 KB
testcase_07 AC 8 ms
20,096 KB
testcase_08 AC 125 ms
30,060 KB
testcase_09 WA -
testcase_10 AC 150 ms
32,972 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 115 ms
29,588 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 108 ms
30,400 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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for(int i=(a); i<(n); ++i)
#define per(i, a, n) for(int i=(a); i>(n); --i)
#define pb emplace_back
#define mp make_pair
#define clr(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x & -x)
#define fi first
#define se second
#define lson o<<1
#define rson o<<1|1
#define gmid l[o]+r[o]>>1

using LL = long long;
using ULL = unsigned long long;
using pii = pair<int,int>;
using PLL = pair<LL, LL>;
using UI = unsigned int;

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1.0);

const int N = 2e5 + 10;

vector<int> V[N], G[N], A[N];
vector<pii> ans;
int n, m, pre[N], deg[N], low[N], idx[N], scc, dfs_cnt, val[N], idx2[N];
stack<int> st;
int com;

void bfs(int x){
	queue<int> Q;
	Q.emplace(x);
	idx2[x] = ++com;

	while(!Q.empty()){
		x = Q.front(); Q.pop();

		for(int j : G[x]){
			if(!idx2[j]){
				idx2[j] = com;
				Q.emplace(j);
			}
		}
	}

}

void dfs(int u){
	pre[u] = low[u] = ++dfs_cnt;
	st.push(u);
	for(int v : V[u]){
		if(!pre[v]){
			dfs(v);
			low[u] = min(low[u], low[v]);
		} else if(!idx[v]){
			low[u] = min(low[u], pre[v]);
		}
	}
	if(low[u] == pre[u]){
		scc++;
		for(;;){
			int x = st.top(); st.pop();
			idx[x] = scc;
			G[scc].pb(x);
			if(x == u)	break;
		}
	}
}

int main(){
	scanf("%d %d", &n, &m);
	int x, y;
	while(m--){
		scanf("%d %d", &x, &y);
		V[x].pb(y);

		G[x].pb(y);
		G[y].pb(x);
	}

	clr(idx2, 0);
	com = 0;
	rep(i, 1, n + 1){
		if(!idx2[i]){
			bfs(i);
		}
	}

	rep(i, 1, n + 1)	G[i].clear();

	clr(pre, 0);
	clr(idx, 0);
	dfs_cnt = scc = 0;

	rep(i, 1, n + 1){
		if(!pre[i]){
			dfs(i);
		}
	}

	rep(i, 1, scc+1){
		val[i] = G[i][0];
		for(int j=1; j<G[i].size(); ++j){
			ans.pb(G[i][j-1], G[i][j]);
		}
		if(G[i].size() > 1){
            ans.pb(G[i].back(), G[i][0]);
		}
		deg[i] = 0;
		G[i].clear();
	}

	rep(i, 1, n + 1){
		x = idx[i];
		for(int j : V[i]){
			y = idx[j];
			if(x == y)	continue;
			G[x].pb(y);
			++deg[y];
		}
	}

	queue<int> Q;
	rep(i, 1, scc + 1){
		if(deg[i] == 0){
			Q.emplace(i);
		}
	}

	while(!Q.empty()){
		x = Q.front(); Q.pop();
		A[idx2[val[x]]].pb(val[x]);
		for(int j : G[x]){
			if(--deg[j] == 0){
				Q.emplace(j);
			}
		}
	}

	rep(i, 1, com+1){
		rep(j, 1, A[i].size()){
			ans.pb(A[i][j-1], A[i][j]);
		}
	}

	printf("%d\n", (int)ans.size());
	for(pii p : ans)	printf("%d %d\n", p.fi, p.se);

	return 0;
}
0