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;
const int N = 5000 + 10;
vector<int> G[N], I[N];
bool good[N], dead[N];
bool R[N], seen[N][N];
vector<int> st;
bool S[N];
int scc[N];
int n;
bool dfs(int v, int s)
{
seen[v][s] = true;
if(good[v]) return 1;
bool ok = 0;
for(int u : G[v])
{
if(seen[u][s] || dead[u]) continue;
ok |= dfs(u, s);
}
return ok;
}
void dfs_scc(int v)
{
S[v] = true;
for(int u : G[v])
if(!S[u] && !dead[u])
dfs_scc(u);
st.push_back(v);
}
void dfs_inv_scc(int v, int sc)
{
S[v] = true;
scc[v] = sc;
for(int u : I[v])
if(!S[u] && !dead[u])
dfs_inv_scc(u, sc);
}
void find_good()
{
for(int i = 0; i < n; i ++)
S[i] = false, I[i].clear(), scc[i] = -1;
for(int i = 0; i < n; i ++)
{
for(int u : G[i])
I[i].push_back(u);
if(dead[i]) continue;
dfs_scc(i);
}
for(int i = 0; i < n; i ++) S[i] = false;
while(st.size())
{
int u = st.back();
st.pop_back();
if(S[u]) continue;
dfs_inv_scc(u, u);
}
}
vector<int> Arezou()
{
vector<int> w(n);
find_good();
// a vertex is good if in its scc we have one charged vertex and at least have 1 edge
int e[n] = {}, ch[n] = {};
for(int i = 0; i < n; i ++)
{
ch[scc[i]] += R[i];
for(int u : G[i])
if(scc[i] == scc[u])
e[scc[i]]++;
}
for(int i = 0; i < n; i++)
good[i] = (ch[scc[i]] > 0 && e[scc[i]] > 0);
for(int s = 0; s < n; s++)
w[s] = dfs(s, s);
return w;
}
vector<int> Borzou()
{
for(int i = 0; i < n; i ++)
dead[i] = R[i];
vector<int> w(n);
find_good();
int e[n] = {};
for(int i = 0; i < n; i ++)
{
if(dead[i]) continue;
for(int u : G[i])
if(scc[i] == scc[u])
e[scc[i]]++;
}
for(int i = 0; i < n; i ++)
if(!dead[i])
good[i] = (e[scc[i]] > 0);
for(int s = 0; s < n; s++)
w[s] = dfs(s, s);
return w;
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
n = a.size();
for(int i = 0; i < n; i ++)
{
G[i].clear(), I[i].clear();
R[i] = S[i] = good[i] = dead[i] = false;
for(int j = 0; j < n; j ++)
seen[i][j] = false;
}
for(int i = 0; i < u.size(); i ++)
G[u[i]].push_back(v[i]);
for(int i = 0; i < n; i ++)
R[i] = r[i];
vector<int> w(n);
int c = count(a.begin(), a.end(), 1);
//if(c == a.size())
//return Arezou();
if(c == 0)
return Borzou();
for(int i = 0; i < n; i++)
{
int s = i;
while(true)
{
// do I have a cycle
bool cycle = false;
for(int c : G[s])
if(c == s) cycle = true;
if(cycle)
{
if(G[s].size() == 1)
{
w[i] = r[s];
break;
}
if(r[s])
{
if(a[s] == 1)
{
w[i] = 1;
break;
}
s++;
continue;
}
if(a[s] == 1)
{
s++;
continue;
}
else
{
w[i] = 0;
break;
}
}
else
{
if(G[s].size())
s++;
else
{
w[i] = 0;
break;
}
}
}
}
return w;
}
Compilation message (stderr)
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i = 0; i < u.size(); i ++)
| ~~^~~~~~~~~~
# | 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... |