| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 921945 | HuyQuang_re_Zero | Toy Train (IOI17_train) | C++14 | 0 ms | 0 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 <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
//#include "train.h"
int d[5005],own[N],is_charge[N],U[N],V[N],n,m,i,u,v,res[N],deg[5005];
vector <int> a[N];
vector <int> who_wins(vector <int> _own,vector <int> _is_charge,vector <int> _U,vector <int> _V)
{
for(i=0;i<_own.size();i++)
{
n++;
own[n]=_own[i]; is_charge[n]=_is_charge[i];
}
for(i=0;i<_U.size();i++)
{
m++;
U[m]=_U[i]+1; V[m]=_V[i]+1;
}
memset(res,-1,sizeof(res));
while(1)
{
auto BFS=[&](vector <int> vec,int ok)
{
memset(d,0,sizeof(d));
queue <int> q;
for(int u:vec) q.push(u),d[u]=1;
while(q.size()>0)
{
int u=q.front(); q.pop();
for(int v:a[u])
{
deg[v]--;
if(d[v]==0 && (deg[v]==0 || own[v]==ok))
q.push(v),d[v]=1;
}
}
};
vector <int> vec;
for(u=1;u<=n;u++) a[u].clear();
memset(deg,0,sizeof(deg));
for(i=1;i<=m;i++)
{
u=U[i]; v=V[i];
if(res[u]==-1 && res[v]==-1)
a[v].push_back(u),deg[u]++;
}
for(u=1;u<=n;u++)
if(res[u]==-1 && is_charge[u])
vec.push_back(u);
BFS(vec,1);
vec.clear();
for(u=1;u<=n;u++)
if(res[u]==-1 && d[u]==0)
vec.push_back(u);
if(vec.size()==0)
{
for(u=1;u<=n;u++)
if(res[u]==-1) res[u]=1;
break;
}
BFS(vec,0);
for(u=1;u<=n;u++)
if(res[u]==-1 && d[u]==1)
res[u]=0;
}
vector <int> w;
for(u=1;u<=n;u++) w.push_back(res[u]);
return w;
}
int main()
{
// freopen("train.inp","r",stdin);
//freopen("train.out","w",stdout);
int n,m,k; cin>>n>>m;
vector <int> own,is_charge,U,V;
for(int i=1;i<=n;i++) cin>>k,own.push_back(k);
for(int i=1;i<=n;i++) cin>>k,is_charge.push_back(k);
for(int i=1;i<=m;i++) cin>>u,U.push_back(u);
for(int i=1;i<=m;i++) cin>>v,V.push_back(v);
vector <int> w=who_wins(own,is_charge,U,V);
for(int k:w) cout<<k<<" ";
}