Submission #641141

#TimeUsernameProblemLanguageResultExecution timeMemory
641141ggohToy Train (IOI17_train)C++14
100 / 100
595 ms1280 KiB
#include "train.h" #include<bits/stdc++.h> using namespace std; #define sz(v) ((int)(v).size()) int n,m,dif,ch[5005],sz[5005],out[5005]; vector<int>rev[5005]; vector<int>A,R; 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[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) { for(int i=0;i<n;i++)if(!R[i])ch[i]=0; f(1); f(0); if(!dif)break; } } 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++) { sz[u[i]]++; rev[v[i]].push_back(u[i]); } for(int i=0;i<n;i++)ch[i]=R[i]; 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...