# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
371799 | stonejjun03 | Toy Train (IOI17_train) | C++14 | 2100 ms | 49132 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<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
ll ans[1010101];
ll chk[1010101];
ll ind[1010101];
ll cnt[1010101];
ll vis[1010101];
ll vis2[1010101];
ll gp[1010101];
queue<ll> q;
vector<ll> v[1010101];
vector<ll> rev[1010101];
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> s) {
ll i,j,k,l,m,n=a.size();
std::vector<int> res(n);
for(i=0;i<u.size();i++){
v[u[i]].pb(s[i]);
rev[s[i]].pb(u[i]);
ind[u[i]]++;
}
ll fl=1;
while(fl){
fl=0;
for(i=0;i<n;i++){
vis[i]=0;
cnt[i]=0;
chk[i]=0;
if(r[i]==1)
vis[i]=1, q.push(i);
}
while(q.size()){
ll x=q.front(); q.pop();
chk[x]=1;
for(auto k:rev[x]){
if(vis[k]) continue;
cnt[k]++;
if(a[k]==1&&cnt[k]==1) vis[k]=1,q.push(k);
if(a[k]==0&&cnt[k]==ind[k]) vis[k]=1,q.push(k);
}
}
for(i=0;i<n;i++){
cnt[i]=0;
ans[i]=vis[i];
vis2[i]=0;
if(chk[i]==0)
vis2[i]=1,q.push(i);
}
while(q.size()){
ll x=q.front(); q.pop();
chk[x]=0;
for(auto k:rev[x]){
if(vis2[k]) continue;
cnt[k]++;
if(a[k]==0&&cnt[k]==1) vis2[k]=1,q.push(k);
if(a[k]==1&&cnt[k]==ind[k]) vis2[k]=1,q.push(k);
}
}
for(i=0;i<n;i++){
if(r[i]&&chk[i]==0){
r[i]==0;
fl=1;
}
}
}
for(i=0;i<n;i++)
res[i]=chk[i];
return res;
}
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... |