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;
#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;
if(p==1)
{
for(int i=0;i<n;i++)
{
if(ch[i])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])
{
if(A[k] || out[k]==0)
{
ch[k]=1;
Q.push(k);
}
}
}
}
}
else
{
for(int i=0;i<n;i++)
{
if(!ch[i])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])
{
if(!A[k] || out[k]==0)
{
ch[k]=0;
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 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... |