Submission #757661

#TimeUsernameProblemLanguageResultExecution timeMemory
757661Rafi22Toy Train (IOI17_train)C++14
100 / 100
329 ms1656 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define st first #define nd second #define pb push_back #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define ll long long ll mod=1000000007; int inf=1000000007; ll infl=1000000000000000007; const int N=5007; int a[N],r[N]; vector<int>G[N]; vector<int>RG[N]; int ile[N]; bool is[N]; vector<int> who_wins(vector<int>a,vector<int>r,vector<int>U,vector<int>V) { int n=sz(a),m=sz(U); vector<int>ans(n,1); for(int i=0;i<m;i++) { G[U[i]].pb(V[i]); RG[V[i]].pb(U[i]); } while(true) { memset(ile,0,sizeof ile); memset(is,0,sizeof is); deque<int>Q; for(int i=0;i<n;i++) { if(r[i]) { Q.pb(i); is[i]=1; } } while(sz(Q)>0) { int v=Q[0]; Q.pop_front(); for(auto u:RG[v]) { if(is[u]) continue; ile[u]++; if(a[u]==1||ile[u]==sz(G[u])) { is[u]=1; Q.pb(u); } } } bool xd=0; for(int i=0;i<n;i++) if(!is[i]) ans[i]=0; for(int i=0;i<n;i++) { if(!r[i]) continue; int c=0; for(auto u:G[i]) if(is[u]) c++; if(c==0||(a[i]==0&&c!=sz(G[i]))) { r[i]=0; xd=1; break; } } if(!xd) break; } return ans; } /* vector<int> who_wins1(vector<int>a,vector<int>r,vector<int>U,vector<int>V) { int n=sz(a),m=sz(U); vector<int>DP(n,0); vector<int>p(n,0); vector<int>q(n,0); for(int i=0;i<m;i++) { if(U[i]==V[i]) p[U[i]]=1; else q[U[i]]=1; } for(int i=n-1;i>=0;i--) { if(q[i]) DP[i]=DP[i+1]; else DP[i]=r[i]; if(p[i]) { if(a[i]==0&&r[i]==0) DP[i]=0; if(a[i]==1&&r[i]==1) DP[i]=1; } } return DP; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; vector<int>a(n),r(n); for(int i=0;i<n;i++) { a[i]=rand()%2; cout<<a[i]<<" "; } cout<<endl; for(int i=0;i<n;i++) { r[i]=rand()%2; cout<<r[i]<<" "; } cout<<endl; vector<int>U,V; for(int i=0;i<n-1;i++) { int t=rand()%3; if(t==0||t==2) { U.pb(i); V.pb(i); } if(t==1||t==2) { U.pb(i); V.pb(i+1); } } U.pb(n-1); V.pb(n-1); for(auto a:U) cout<<a<<" "; cout<<endl; for(auto a:V) cout<<a<<" "; cout<<endl; vector<int>x=who_wins(a,r,U,V); vector<int>y=who_wins1(a,r,U,V); for(auto a:x) cout<<a<<" "; cout<<endl; for(auto a:y) cout<<a<<" "; cout<<endl; return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...