結果
問題 | No.2780 The Bottle Imp |
ユーザー |
|
提出日時 | 2024-06-07 22:37:00 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,681 bytes |
コンパイル時間 | 3,052 ms |
コンパイル使用メモリ | 219,032 KB |
実行使用メモリ | 36,752 KB |
最終ジャッジ日時 | 2024-12-27 14:13:09 |
合計ジャッジ時間 | 5,940 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 WA * 1 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/scc>using namespace std;using ll=long long;#define rep(i,s,t) for(ll i=s;i<(ll)(t);i++)#define rrep(i,s,t) for(ll i=(ll)(t)-1;i>=(ll)s;i--)#define all(x) begin(x),end(x)#define rall(x) rbegin(x),rend(x)#define TT template<typename T>TT using vec=vector<T>;TT bool chmin(T &x,T y){return x>y?(x=y,true):false;}TT bool chmax(T &x,T y){return x<y?(x=y,true):false;}struct io_setup{io_setup(){ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(15);}} io_setup;int main(){int N;cin>>N;atcoder::scc_graph G(N);vector<vector<int>>to(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.add_edge(i,a);to[i].push_back(a);}}vector<vector<int>>S=G.scc();vector<int>id(N);int L=S.size();for(int i=0;i<L;i++){for(auto x:S[i]){id[x]=i;}}vector<vector<int>>g(L);for(int i=0;i<N;i++){for(auto j:to[i]){if(id[i]!=id[j])g[id[i]].push_back(id[j]);}}vector<bool>flag(L);flag[id[0]]=true;queue<int>q;q.push(id[0]);vector<int>dp(L,-(1<<30));dp[id[0]]=1;while(q.size()){int x=q.front();q.pop();for(auto i:g[x]){if(!flag[i]){flag[i]=true;chmax(dp[i],dp[x]+1);q.push(i);}}}int ma=0;for(int i=0;i<L;i++)chmax(ma,dp[i]);if(ma==L)cout<<"Yes\n";else cout<<"No\n";}