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>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
using namespace std;
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
int n = ssize(a);
int m = ssize(u);
vector<int> ret(n);
vector<vector<int>> g(n);
REP(i, m) g[u[i]].emplace_back(v[i]);
bool sciezka = 1;
REP(i, m) if(u[i] != v[i] && v[i] != u[i]+1) sciezka = 0;
if(sciezka){
for(int i = n; ~--i;){
bool petla = 0, dalej = 0;
for(int j : g[i]){
if(j == i) petla = 1;
if(j == i+1) dalej = 1;
}
if(a[i]){
ret[i] = 0;
if(petla && r[i]) ret[i] |= 1;
if(dalej) ret[i] |= ret[i+1];
}
else{
ret[i] = 1;
if(petla && !r[i]) ret[i] &= 0;
if(dalej) ret[i] &= ret[i+1];
}
}
return ret;
}
bool wszystkie_a = 1;
REP(i, n) if(!a[i]) wszystkie_a = 0;
if(wszystkie_a){
vector<int> czy_cykl(n, 0);
REP(start, n){
vector<bool> odw(n, 0);
function<void(int)> dfs = [&](int w){
odw[w] = 1;
for(int i : g[w]){
if(i == start) czy_cykl[start] = 1;
if(!odw[i]) dfs(i);
}
};
dfs(start);
}
REP(start, n){
vector<bool> odw(n, 0);
function<void(int)> dfs = [&](int w){
odw[w] = 1;
if(r[w] && czy_cykl[w]) ret[start] = 1;
for(int i : g[w]) if(!odw[i]) dfs(i);
};
dfs(start);
}
return ret;
}
bool wszystkie_b = 1;
REP(i, n) if(a[i]) wszystkie_b = 0;
if(wszystkie_b){
vector<int> czy_cykl(n, 0);
REP(start, n) if(!r[start]){
vector<bool> odw(n, 0);
function<void(int)> dfs = [&](int w){
odw[w] = 1;
for(int i : g[w]) if(!r[i]){
if(i == start) czy_cykl[start] = 1;
if(!odw[i]) dfs(i);
}
};
dfs(start);
}
REP(start, n){
ret[start] = 1;
vector<bool> odw(n, 0);
function<void(int)> dfs = [&](int w){
odw[w] = 1;
if(czy_cykl[w]) ret[start] = 0;
for(int i : g[w]) if(!odw[i]) dfs(i);
};
dfs(start);
}
return ret;
}
REP(i, n){
}
return ret;
}
# | 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... |