| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 769626 | APROHACK | 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 "train.h"
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define past 2
#define ancestor 1
#define unvisited 0
using namespace std;
int n;
vector<bool>owner, charging;
vector<int>adj[5001];
vector<int>adjInverso[5001];
bool isCycle[5001][2] ; // 0 Negative 1 Positive
short int vis[5001];
vector<int>nodos;
void memss(){
for(int i = 0 ; i < n ; i ++)vis[i] = 0;
}
bool dfs(int node){
////cout << "were " << node << endl;
bool isA = owner[node];
bool isCharging = charging[node];
vis[node] = 1;
nodos.pb(node);
for(int i = 0 ; i < adj[node].size() ; i ++){
if(!vis[adj[node][i]]){
if(dfs(adj[node][i]) == isA){
nodos.pop_back();
vis[node] = 0;
return isA;
}
}else{
bool hayC = false;
for(int j = nodos.size()-1 ; j>= 0 ; j --){
if(charging[nodos[j]])hayC = true;
if(nodos[j] == adj[node][i])break;
}
if((hayC && isA) or (!hayC && !isA)){
nodos.pop_back();
vis[node] = 0;
}
if(hayC && isA)return true;
else if(!hayC && !isA)return false;
}
}
nodos.pop_back();
vis[node] = 0;
return !isA;
}
void recorrer(int node){
vis[node] = ancestor;
nodos.pb(node);
for(int i = 0 ; i < adj[node].size() ; i ++){
if(vis[adj[node][i]] == past)continue;
if(vis[adj[node][i]] == ancestor){
bool positive = false;
for(int j = nodos.size()-1 ; j >= 0 ; j --){
if(charging[nodos[j]]){
positive = true;
break;
}
if(nodos[j] == adj[node][i])break;
}
for(int j = nodos.size() - 1 ; j >= 0 ; j --){
if(positive)isCycle[nodos[j]][1] = true;
else isCycle[nodos[j]][0] = true;
if(nodos[j] == adj[node][i])break;
}
}else{
recorrer(adj[node][i]);
}
}
vis[node] = past;
nodos.pop_back();
}
void dfs2(int node, int isCyclePos){
isCycle[node][isCyclePos] = true;
vis[node] = past;
for(int i = 0 ; i < adjInverso[node].size() ; i ++){
if(vis[adjInverso[node][i] ] == past)continue;
dfs2(adjInverso[node][i], isCyclePos);
}
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
n = a.size();
vector<int> res;
memss();
bool all1 = true, all0 = true;
for(int i = 0 ; i < n ; i ++){
isCycle[i][0] = false;
isCycle[i][1] = false;
owner.pb(a[i]);
res.pb(0);
charging.pb(r[i]);
if(a[i] == 0)all1 = false;
else all0 = false;
}
for(int i = 0 ; i < u.size() ; i ++){
adj[u[i]].pb(v[i]);
adjInverso[v[i]].pb(u[i]);
}
if(all0 or all1){
memset(ansFor, -1, sizeof ansFor);
for(int i = 0 ; i < n ; i ++){
if(vis[i] == unvisited)recorrer(i);
}
memss();
for(int i = 0 ; i < n ; i++){
if(all1 and isCycle[i][1]){
dfs2(i, 1);
}else if(all0 and isCycle[i][0]){
dfs2(i, 0);
}
}
for(int i = 0 ; i < n ; i ++){
if(all1 and isCycle[i][1])res[i] = 1;
else if (all1)res[i] = 0;
else if(isCycle[i][0])res[i] = 0;
else res[i] = 1;
}
}else{
for(int i = 0 ; i < n ; i ++){
if(dfs(i)){
res[i] = 1;
}else res[i] = 0;
ansFor[i] = res[i];
}
}
return res;
}