# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
767297 | APROHACK | Toy Train (IOI17_train) | C++14 | 2073 ms | 1236 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];
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();
}
int ansFor[5001];
bool dfs2(int node){
bool isA = owner[0];
if(isA and isCycle[node][1])return true;
if(!isA and isCycle[node][0])return false;
if(ansFor[node] != -1)return ansFor[node];
vis[node] = past;
for(int i = 0 ; i < adj[node].size() ; i ++){
if(vis[adj[node][i] ] == past)continue;
if(dfs2(adj[node][i]) == isA){
vis[node] = unvisited;
ansFor[node] = (isA ? 1 : 0);
return ansFor[node];
}
}
vis[node] = unvisited;
return !isA;
}
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 ++){
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]);
}
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(dfs2(i)){
res[i] = 1;
}else res[i] = 0;
}
}else{
for(int i = 0 ; i < n ; i ++){
if(dfs(i)){
res[i] = 1;
}else res[i] = 0;
ansFor[i] = res[i];
}
}
return res;
}
Compilation message (stderr)
# | 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... |