結果

問題 No.2780 The Bottle Imp
ユーザー GOTKAKOGOTKAKO
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0