| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 612436 | MohamedAliSaidane | Wiring (IOI17_wiring) | 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>
//#include "train.h"
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
const int nax = 5004;
const int MOD = 1e9 + 7;
int C[nax];
vi adj[nax];
vi rev_adj[nax];
int A[nax];
int n, m;
int dp[nax][nax];
int vis[nax], self[nax], ok[nax];
vi order, comp;
void dfs(int x)
{
vis[x] = 1;
for(auto e: adj[x])
{
if(!vis[e])
dfs(e);
}
order.pb(x);
}
void dfs1(int x)
{
vis[x] = 1;
for(auto e: rev_adj[x])
if(!vis[e])
dfs1(e);
comp.pb(x);
}
vi who_wins(vi a, vi r, vi u, vi v)
{
memset(dp, -1,sizeof(dp));
n = a.size();
m = u.size();
for(int i = 0 ; i < n; i++)
{
A[i] = a[i];
C[i] = r[i];
}
for(int i= 0; i < m; i++)
{
adj[u[i]].pb(v[i]);
rev_adj[v[i]].pb(u[i]);
if(u[i] == v[i])
self[u[i]] = 1;
}
for(int i = 0 ; i < n;i ++)
if(!vis[i])
dfs(i);
reverse(all(order));
memset(vis, false,sizeof(vis));
for(auto e: order)
{
if(vis[e])
continue;
comp.clear();
dfs1(e);
if(comp.size() > 1)
{
for(auto e: comp)
ok[e] = 1;
}
else if(self[comp[0]])
ok[comp[0]] = 1;
}
queue<pii> q;
int sp[n + 1];
for(int i = 0; i < n; i++)
{
if(ok[i] && !C[i])
{
sp[i] = 0;
q.push({i, 0});
}
else
sp[i] = MOD;
}
while(!q.empty())
{
int node = q.front().ff;
int dis = q.front().ss;
q.pop();
for(auto e: rev_adj[node])
{
if(sp[e] > dis + 1)
{
sp[e] = dis + 1;
q.push({e, dis + 1});
}
}
}
vi ans;
for(int i= 0 ; i < n; i ++ )
{
if(sp[i] <= n)
ans.pb(0);
else
ans.pb(1);
}
return ans;
}