# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70852 | Kmcode | Toy Train (IOI17_train) | C++14 | 749 ms | 1904 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 <bits/stdc++.h>
using namespace std;
//#include "train.h"
vector<int> v[5002];
vector<int> rv[5002];
bool use[5002];
int sz[5002];
vector<int> bc;
inline void dfs(int b){
use[b]=true;
for(int go:v[b]){
if(use[go]==false){
dfs(go);
}
}
bc.push_back(b);
}
int belong[5002];
inline void dfs2(int b,int be){
use[b]=false;
belong[b]=be;
sz[be]++;
for(int go:rv[b]){
if(use[go]){
dfs2(go,be);
}
}
}
int m;
int n;
void scc(){
for(int i=0;i<n;i++){
if(use[i]==false){
dfs(i);
}
}
reverse(bc.begin(),bc.end());
for(int i=0;i<bc.size();i++){
if(use[bc[i]]){
dfs2(bc[i],m);
m++;
}
}
}
vector<int> ed[5002];
bool ok[5002];
int us[5002];
int u_s;
bool bor[5002];
bool are[5002];
vector<int> r;
inline bool a_walk(int node){
us[node]=u_s;
if(are[node])return true;
if(ok[belong[node]]==false&&sz[belong[node]]>1)return true;
for(int go:v[node]){
if(us[go]!=u_s){
if(a_walk(go))return true;
}
}
return false;
}
inline bool b_walk(int node){
us[node]=u_s;
if(bor[node])return true;
if(sz[belong[node]]>1)return true;
for(int go:v[node]){
if(us[go]!=u_s){
if(b_walk(go))return true;
}
}
return false;
}
std::vector<int> who_wins(std::vector<int> a1, std::vector<int> r1, std::vector<int> u1, std::vector<int> v1) {
r=r1;
n=a1.size();
for(int i=0;i<u1.size();i++){
if(u1[i]==v1[i]){
if(r1[u1[i]]){
are[u1[i]]=true;
}
else{
bor[u1[i]]=true;
}
continue;
}
if(r[u1[i]]||r[v1[i]])continue;
v[u1[i]].push_back(v1[i]);
rv[v1[i]].push_back(u1[i]);
}
scc();
for(int i=0;i<n;i++){
ok[belong[i]]|=r1[i];
}
vector<int> ret(a1.size(),1);
for(int i=0;i<n;i++)v[i].clear();
for(int i=0;i<u1.size();i++)v[u1[i]].push_back(v1[i]);
for(int i=0;i<n;i++){
u_s++;
if(a_walk(i)){
ret[i]=0;
}
}
return ret;
}
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... |