結果
問題 | No.2780 The Bottle Imp |
ユーザー |
![]() |
提出日時 | 2024-06-07 22:17:06 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 2,735 bytes |
コンパイル時間 | 4,137 ms |
コンパイル使用メモリ | 272,472 KB |
実行使用メモリ | 52,344 KB |
最終ジャッジ日時 | 2024-12-27 13:55:42 |
合計ジャッジ時間 | 8,866 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pll=pair<ll,ll>;using tll=tuple<ll,ll,ll>;using ld=long double;const ll INF=(1ll<<60);#define rep(i,n) for (ll i=0;i<(ll)(n);i++)#define replr(i,l,r) for (ll i=(ll)(l);i<(ll)(r);i++)#define all(v) v.begin(),v.end()#define len(v) ((ll)v.size())template<class T> inline bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}template<class T> inline bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}struct SCC{int n;vector<vector<int>> g,rg;vector<bool> used;vector<int> ord;vector<int> comp;SCC(int x){n=x;g.resize(n);rg.resize(n);used.resize(n,false);comp.resize(n,-1);}void add_edge(int u,int v){g[u].push_back(v);rg[v].push_back(u);}void dfs(int x){used[x]=true;for(auto &i:g[x]){if(!used[i]) dfs(i);}ord.push_back(x);}void rdfs(int x,int cnt){comp[x]=cnt;for(auto &i:rg[x]){if(comp[i]==-1) rdfs(i,cnt);}}vector<vector<int>> solve(){for(int i=0;i<n;i++){if(used[i]) continue;dfs(i);}reverse(ord.begin(),ord.end());int cnt=0;for(auto &i:ord){if(comp[i]!=-1) continue;rdfs(i,cnt);cnt++;}vector<vector<int>> ret(cnt);for(int i=0;i<n;i++){ret[comp[i]].push_back(i);}return ret;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);ll n;cin >> n;vector<vector<ll>> g(n);rep(i,n){ll m;cin >> m;rep(j,m){ll a;cin >> a;a--;g[i].push_back(a);}}SCC s(n);rep(i,n){for(auto j:g[i]) s.add_edge(i,j);}vector<vector<int>> ret=s.solve();ll sz=len(ret);vector<set<ll>> st(sz);vector<ll> v(n);rep(i,sz){for(auto j:ret[i]){st[i].insert(j);v[j]=i;}}vector<set<ll>> h(sz);rep(i,sz){for(auto j:ret[i]){for(auto k:g[j]){if(st[i].contains(k)) continue;h[i].insert(v[k]);}}}vector<ll> dp(sz,0);rep(i,sz){if(st[i].contains(0)) dp[i]=1;}rep(i,sz){if(dp[i]==0) continue;for(auto j:h[i]){chmax(dp[j],dp[i]+1);}}if(dp[sz-1]==sz) cout << "Yes\n";else cout << "No\n";}