# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
53200 | WA_TLE | Toy Train (IOI17_train) | C++14 | 703 ms | 11772 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "train.h"
#include<vector>
#include<queue>
using namespace std;
#define pub push_back
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
int i,j,n=a.size(),m=u.size();
vector<vector<int>>go(n);
vector<vector<int>>rev(n);
//サイクルになりうるのを求める
for(i=0;i<m;i++){
go[u[i]].pub(v[i]);
rev[v[i]].pub(u[i]);
}
//cirが0以下ならチャー駅に行ける(勝つとは言ってない)
//0より大きいなら即Bの勝ち
vector<int>ans(n,1);
while(-1){
vector<int>cir(n);
queue<int>que;
for(i=0;i<n;i++){
if(r[i]&&ans[i]){que.push(i);}
else if(a[i]){cir[i]=1;}
else{cir[i]=go[i].size();}
}
while(que.size()>0){
int ter=que.front();
que.pop();
for(auto it:rev[ter]){
if(cir[it]==1){que.push(it);}
cir[it]--;
}
}
vector<int>bwi(n);
for(i=0;i<n;i++){
if(cir[i]>0){que.push(i);}
else if(a[i]){bwi[i]=go[i].size();}
else{bwi[i]=1;}
}
while(que.size()>0){
int ter=que.front();
que.pop();
for(auto it:rev[ter]){
if(bwi[it]==1){que.push(it);}
bwi[it]--;
}
}
vector<int>gen(n);
for(i=0;i<n;i++){if(bwi[i]>0){gen[i]=1;}}
if(ans==gen){return gen;}
else{ans=move(gen);}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |