結果
問題 | No.1553 Lovely City |
ユーザー | 01fe18bcs175 rohan |
提出日時 | 2021-06-18 23:45:20 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 455 ms / 2,000 ms |
コード長 | 2,197 bytes |
コンパイル時間 | 1,066 ms |
コンパイル使用メモリ | 87,356 KB |
実行使用メモリ | 25,080 KB |
最終ジャッジ日時 | 2023-09-05 00:24:32 |
合計ジャッジ時間 | 13,540 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
8,868 KB |
testcase_01 | AC | 5 ms
8,792 KB |
testcase_02 | AC | 32 ms
21,056 KB |
testcase_03 | AC | 5 ms
8,820 KB |
testcase_04 | AC | 5 ms
8,816 KB |
testcase_05 | AC | 6 ms
8,820 KB |
testcase_06 | AC | 5 ms
8,820 KB |
testcase_07 | AC | 6 ms
8,832 KB |
testcase_08 | AC | 291 ms
17,100 KB |
testcase_09 | AC | 316 ms
17,640 KB |
testcase_10 | AC | 337 ms
21,640 KB |
testcase_11 | AC | 245 ms
17,072 KB |
testcase_12 | AC | 347 ms
22,652 KB |
testcase_13 | AC | 263 ms
16,176 KB |
testcase_14 | AC | 288 ms
17,424 KB |
testcase_15 | AC | 266 ms
18,084 KB |
testcase_16 | AC | 338 ms
18,156 KB |
testcase_17 | AC | 256 ms
18,632 KB |
testcase_18 | AC | 455 ms
25,080 KB |
testcase_19 | AC | 442 ms
25,024 KB |
testcase_20 | AC | 447 ms
24,932 KB |
testcase_21 | AC | 451 ms
24,732 KB |
testcase_22 | AC | 447 ms
24,628 KB |
testcase_23 | AC | 446 ms
24,952 KB |
testcase_24 | AC | 446 ms
24,900 KB |
testcase_25 | AC | 439 ms
25,020 KB |
testcase_26 | AC | 445 ms
24,672 KB |
testcase_27 | AC | 450 ms
25,012 KB |
ソースコード
#include <iostream> #include <queue> using namespace std; typedef pair<int, int> P; struct Graph { int n; std::vector<std::vector<int>> g; Graph(){} Graph(int n) : n(n){ g.resize(n); } void add_edge(int from, int to){ g[from].push_back(to); } }; struct UnionFind { std::vector<int> par, sz; UnionFind(int n){ par.resize(n); sz.resize(n); for(int i = 0; i < n; i++){ par[i] = i; sz[i] = 1; } } int find(int i){ if(i == par[i]) return i; return par[i] = find(par[i]); } bool same(int i, int j){ return find(i) == find(j); } void unite(int i, int j){ i = find(i), j = find(j); if(i == j) return; if(sz[i] < sz[j]) std::swap(i, j); par[j] = i; sz[i] += sz[j]; } int size(int i){ return sz[find(i)]; } }; vector<int> y[200005]; int main() { int n, m; cin >> n >> m; Graph g(n); UnionFind uf(n); int d[200005]{0}; for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; g.add_edge(u, v); uf.unite(u, v); d[v]++; } for(int u = 0; u < n; u++){ y[uf.find(u)].push_back(u); } vector<P> ans; for(int r = 0; r < n; r++){ if(uf.find(r) != r) continue; int l = -1; vector<P> t; queue<int> que; for(int u : y[r]){ if(!d[u]) que.push(u); } while(que.size()){ int u = que.front(); que.pop(); if(l != -1) t.push_back(P(l, u)); l = u; for(int v : g.g[u]){ d[v]--; if(!d[v]) que.push(v); } } if(t.size() == y[r].size() - 1){ for(P p : t) ans.push_back(p); } else{ int k = y[r].size(); for(int i = 0; i < k; i++){ ans.push_back(P(y[r][i], y[r][(i + 1) % k])); } } } cout << ans.size() << endl; for(P p : ans) cout << p.first + 1 << " " << p.second + 1 << endl; }