結果
問題 |
No.2780 The Bottle Imp
|
ユーザー |
![]() |
提出日時 | 2024-06-08 00:46:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 3,651 bytes |
コンパイル時間 | 2,777 ms |
コンパイル使用メモリ | 215,444 KB |
最終ジャッジ日時 | 2025-02-21 20:43:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = 1e9 + 10; const ll INFL = 4e18; struct SCC { vector<vector<int>> members, graph_decomposed; vector<int> group; }; SCC scc_decomposition(const vector<vector<int>> &G) { int n = G.size(); vector<vector<int>> G2(n); for (int i = 0; i < n; i++) { for (int nxt : G[i]) { G2[nxt].push_back(i); } } vector<int> order(n), component(n, -1); vector<bool> vst(n); auto F = [&](auto F, int now) -> void { vst[now] = true; for (int nxt : G[now]) { if (!vst[nxt]) { F(F, nxt); } } order.push_back(now); }; auto F2 = [&](auto F2, int now, int idx) -> void { component[now] = idx; for (int nxt : G2[now]) { if (component[nxt] == -1) { F2(F2, nxt, idx); } } }; for (int i = 0; i < n; i++) { if (!vst[i]) { F(F, i); } } int idx = 0; reverse(order.begin(), order.end()); for (int now : order) { if (component[now] == -1) { F2(F2, now, idx); idx++; } } int n_n = *max_element(component.begin(), component.end()) + 1; vector<vector<int>> ret(n_n); for (int i = 0; i < n; i++) { ret[component[i]].push_back(i); } vector<vector<int>> ret2(n_n); for (int i = 0; i < n; i++) { for (int j : G[i]) { if (component[i] != component[j]) { ret2[component[i]].push_back(component[j]); } } } for (int i = 0; i < n_n; i++) { sort(ret2[i].begin(), ret2[i].end()); ret2[i].erase(unique(ret2[i].begin(), ret2[i].end()), ret2[i].end()); } return {ret, ret2, component}; } bool topological_sort(const vector<vector<int>> &G) { int n = G.size(); vector<int> indeg(n); for (int i = 0; i < n; i++) { for (int nxt : G[i]) { indeg[nxt]++; } } vector<int> ret1, ret2; { priority_queue<int> Q; for (int i = 0; i < n; i++) { if (indeg[i] == 0) { Q.push(i); } } vector<int> ret; while (!Q.empty()) { int now = Q.top(); Q.pop(); for (int nxt : G[now]) { indeg[nxt]--; if (indeg[nxt] == 0) { Q.push(nxt); } } ret.push_back(now); } ret1 = ret; } { priority_queue<int, vector<int>, greater<>> Q; for (int i = 0; i < n; i++) { if (indeg[i] == 0) { Q.push(i); } } vector<int> ret; while (!Q.empty()) { int now = Q.top(); Q.pop(); for (int nxt : G[now]) { indeg[nxt]--; if (indeg[nxt] == 0) { Q.push(nxt); } } ret.push_back(now); } ret2 = ret; } return ret1 == ret2; } int main() { int N; cin >> N; vector<vector<int>> G(N); for (int i = 0; i < N; i++) { int m; cin >> m; for (int j = 0; j < m; j++) { int a; cin >> a; a--; G[i].push_back(a); } } auto [member, nG, group] = scc_decomposition(G); if (group[0] != 0) { cout << "No" << endl; } else if (!topological_sort(nG)) { cout << "No" << endl; } else { cout << "Yes" << endl; } }