Submission #641137

#TimeUsernameProblemLanguageResultExecution timeMemory
641137ggohToy Train (IOI17_train)C++14
100 / 100
658 ms1500 KiB
#include "train.h" #include<bits/stdc++.h> using namespace std; #define sz(v) ((int)(v).size()) int n,m,dif,ch[5005],out[5005]; vector<int>G[5005],rev[5005]; vector<int>A,R,T; void f(int p) { queue<int>Q; dif=0; for(int i=0;i<n;i++) { if(ch[i]==p)Q.push(i); out[i]=sz(G[i]); } while(!Q.empty()) { int q=Q.front();Q.pop(); for(auto &k:rev[q]) { out[k]--; if(ch[k]!=p) { if(A[k]==p || out[k]==0) { ch[k]=p; Q.push(k); dif=1; } } } } } void g() { while(1) { f(0); if(!dif)break; for(int i=0;i<n;i++)if(!R[i])ch[i]=0; f(1); } } vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { n=sz(a);m=sz(u); vector<int> res(n); A=a;R=r; for(int i=0;i<m;i++) { G[u[i]].push_back(v[i]); rev[v[i]].push_back(u[i]); } for(int i=0;i<n;i++)ch[i]=R[i]; f(1); g(); for(int i=0;i<n;i++)res[i]=ch[i]; return res; }
#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...