#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;
int n;
bool is[MAXN],sp[MAXN],ok[MAXN],li[MAXN],dp[MAXN],primka[MAXN];
vector<int> v[MAXN],r[MAXN],ans,g[MAXN];
int tim[MAXN],comp[MAXN],k,sz[MAXN];
bool ban[MAXN],dead[MAXN];
stack<int> st;
void dfs(int x){
li[x]=true;
for(int i:v[x]){
if(!li[i] and !ban[i])dfs(i);
}
st.push(x);
}
void scc(int x){
li[x]=true;
comp[x]=k; sz[k]++;
if(sp[x] or dead[x])ok[k]=true;
for(int i:r[x]){
if(!li[i] and !ban[i])scc(i);
}
}
bool ff(int x){
if(li[x])return dp[x];
li[x]=true;
dp[x]=ok[x];
for(int i:g[x]){
if(ff(i))dp[x]=true;
}
return dp[x];
}
bool brute(int x,int last,int t){
tim[x]=t;
if(sp[x])last=t;
for(int i=0;i<v[x].size();i++){
if(is[x]){
if(tim[v[x][i]]!=0 and tim[v[x][i]]<=last){
tim[x]=0; return true;
}
}else{
if(tim[v[x][i]]!=0 and tim[v[x][i]]>last){
tim[x]=0; return false;
}
}
}
for(int i=0;i<v[x].size();i++){
if(tim[v[x][i]]!=0)continue;
if(is[x]){
if(brute(v[x][i],last,t+1)){
tim[x]=0; return true;
}
}else{
if(!brute(v[x][i],last,t+1)){
tim[x]=0; return false;
}
}
}
tim[x]=0;
return !is[x];
}
vector<int> who_wins(vector<int> A,vector<int> R, vector<int> from,vector<int> to){
n=int(A.size());
int mins=1,maxs=0;
for(int i=1;i<=n;i++){
is[i]=A[i-1];
mins=min(mins,int(is[i]));
maxs=max(maxs,int(is[i]));
sp[i]=R[i-1];
}
for(int i=1;i<=from.size();i++){
from[i-1]++; to[i-1]++;
v[from[i-1]].push_back(to[i-1]);
r[to[i-1]].push_back(from[i-1]);
if(from[i-1]==to[i-1])primka[from[i-1]]=true;
}
if(n<=15){
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++)tim[f]=0;
if(brute(i,0,1))ans.push_back(1);
else ans.push_back(0);
}
}else{
if(mins==maxs and mins==1){
for(int i=1;i<=n;i++){
if(li[i])continue;
dfs(i);
}
for(int i=1;i<=n;i++)li[i]=false;
while(!st.empty()){
if(!li[st.top()]){
k++; scc(st.top());
if(sz[k]==1 and !primka[st.top()])ok[k]=false;
}
st.pop();
}
for(int i=1;i<=from.size();i++){
if(comp[from[i-1]]==comp[to[i-1]])continue;
g[comp[from[i-1]]].push_back(comp[to[i-1]]);
}
for(int i=1;i<=n;i++)li[i]=false;
for(int i=1;i<=n;i++){
if(ff(comp[i]))ans.push_back(1);
else ans.push_back(0);
}
}else if(mins==maxs and mins==0){
cout<<1/0;
for(int i=1;i<=n;i++){
if(sp[i])ban[i]=true;
}
for(int i=1;i<=n;i++){
if(li[i] or ban[i])continue;
dfs(i);
}
for(int i=1;i<=n;i++)li[i]=false;
while(!st.empty()){
if(!li[st.top()]){
k++; scc(st.top());
if(sz[k]>1 or primka[st.top()])ok[k]=true;
}
st.pop();
}
for(int i=1;i<=n;i++){
if(ok[comp[i]])dead[i]=true;
}
for(int i=1;i<=n;i++)li[i]=ban[i]=false;
for(int i=1;i<=n;i++){
if(li[i])continue;
dfs(i);
}
for(int i=1;i<=n;i++)li[i]=false;
k=0;
while(!st.empty()){
if(!li[st.top()]){
k++; ok[k]=false;
scc(st.top());
}
st.pop();
}
for(int i=1;i<=from.size();i++){
if(comp[from[i-1]]==comp[to[i-1]])continue;
g[comp[from[i-1]]].push_back(comp[to[i-1]]);
}
for(int i=1;i<=n;i++)li[i]=false;
for(int i=1;i<=n;i++){
if(ff(comp[i]))ans.push_back(0);
else ans.push_back(1);
}
}
}
return ans;
}
int main(){
ans=who_wins({0, 0}, {1,0}, {0, 0, 1, 1}, {0, 1, 0, 1});
for(int i:ans)cout<<i<<" ";
return 0;
}
Compilation message
train.cpp: In function 'bool brute(int, int, int)':
train.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
train.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=1;i<=from.size();i++){
| ~^~~~~~~~~~~~~
train.cpp:127:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i=1;i<=from.size();i++){
| ~^~~~~~~~~~~~~
train.cpp:140:11: warning: division by zero [-Wdiv-by-zero]
140 | cout<<1/0;
| ~^~
train.cpp:185:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | for(int i=1;i<=from.size();i++){
| ~^~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccYyPoW3.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccchz3F4.o:train.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
