結果
問題 |
No.2780 The Bottle Imp
|
ユーザー |
![]() |
提出日時 | 2024-06-07 22:21:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,489 bytes |
コンパイル時間 | 4,756 ms |
コンパイル使用メモリ | 265,076 KB |
最終ジャッジ日時 | 2025-02-21 20:23:06 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 WA * 1 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; int main() { int n; cin >> n; vector<vector<int>> g(n); scc_graph sg(n); for (int i = 0; i < n; i++) { int m; cin >> m; while (m--) { int j; cin >> j; j--; g[i].push_back(j); sg.add_edge(i, j); } } vector<vector<int>> list = sg.scc(); int sz = list.size(); vector<int> belong(n); for (int i = 0; i < sz; i++) { for (int v : list[i]) { belong[v] = i; } } vector<set<int>> g2(sz); for (int i = 0; i < n; i++) { for (int j : g[i]) { if (belong[i] != belong[j]) { g2[belong[i]].insert(belong[j]); } } } vector<bool> visit(sz, false); int start = belong[0]; queue<int> q; q.push(start); visit[start] = true; while (!q.empty()) { int v = q.front(); q.pop(); for (int nv : g2[v]) { if (visit[nv]) { continue; } visit[nv] = true; q.push(nv); } } for (int i = 0; i < sz; i++) { if (!visit[i]) { cout << "No" << endl; return 0; } } for (int i = 0; i < sz; i++) { if (g2[i].size() >= 2) { cout << "No" << endl; return 0; } } cout << "Yes" << endl; }