結果
問題 | No.2780 The Bottle Imp |
ユーザー |
|
提出日時 | 2024-06-07 21:50:57 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 98 ms / 2,000 ms |
コード長 | 2,160 bytes |
コンパイル時間 | 4,001 ms |
コンパイル使用メモリ | 228,408 KB |
実行使用メモリ | 35,996 KB |
最終ジャッジ日時 | 2024-12-27 13:42:08 |
合計ジャッジ時間 | 7,052 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;class SCC{public:int siz = 0,name = 0,nowc = 0;vector<bool> already;vector<int> ord,low,belong,topo;vector<vector<int>> Graph,cycle;stack<int> St;void dfs(int pos){low.at(pos) = (ord.at(pos) = name++); St.push(pos);for(auto to : Graph.at(pos)){if(ord.at(to) == -1){dfs(to);low.at(pos) = min(low.at(pos),low.at(to));}else if(!already.at(to)) low.at(pos) = min(low.at(pos),ord.at(to));}if(low.at(pos) == ord.at(pos)){cycle.push_back({});while(true){int s = St.top(); St.pop();cycle.back().push_back(s);belong.at(s) = nowc; already.at(s) = true;if(s == pos) break;}nowc++;}}void make(vector<vector<int>> &G){Graph = G; siz = G.size();ord.resize(siz,-1); low.resize(siz,1001001001);already.resize(siz); belong.resize(siz);for(int i=0; i<siz; i++) if(ord.at(i) == -1) dfs(i);for(int i=0; i<siz; i++) belong.at(i) = (nowc-1)-belong.at(i);reverse(cycle.begin(),cycle.end());}};int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int N; cin >> N;vector<vector<int>> Graph(N);for(int i=0; i<N; i++){int K; cin >> K;for(int k=0; k<K; k++){int to; cin >> to; to--;Graph.at(i).push_back(to);}}SCC Z; Z.make(Graph);if(Z.belong.at(0) != 0){cout << "No" << endl; return 0;}reverse(Z.cycle.begin(),Z.cycle.end());set<int> S;bool end = true;for(auto &Vs : Z.cycle){set<int> S2;for(auto pos : Vs) S2.insert(pos);if(end){end = false; S = S2; continue;}bool ok = false;for(auto pos : Vs){for(auto to : Graph.at(pos)) if(S.count(to)){ok = true; break;}if(ok) break;}if(!ok){cout << "No" << endl; return 0;}S = S2; continue;}cout << "Yes" << endl;}