Submission #72862

#TimeUsernameProblemLanguageResultExecution timeMemory
72862Sa1378Toy Train (IOI17_train)C++17
0 / 100
18 ms2132 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; #define N ((int)11*1000) int n,m,cnt; bool self[N],ans[N],mark[N]; vector <int> e[N],er[N],tpl; void dfs(int x,vector <int> &r) { mark[x]=1; for(auto u:e[x]) if(!mark[u] && !r[u]) dfs(u,r); tpl.push_back(x); } void dfs2(int x,vector <int> &r) { mark[x]=1;cnt++; for(auto u:er[x]) if(!mark[u]) dfs2(u,r); } void dfs_ans(int x) { ans[x]=1; for(auto u:er[x]) if(!ans[u]) dfs_ans(u); } vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v) { int n=a.size(),m=u.size(); for(int i=0;i<m;i++) { if(u[i]==v[i])self[u[i]]=1; else e[u[i]].push_back(v[i]),er[v[i]].push_back(u[i]); } for(int i=0;i<n;i++) if(!mark[i] && !r[i]) dfs(i,r); reverse(tpl.begin(),tpl.end()); memset(mark,0,sizeof mark); for(auto u:tpl) if(!mark[u]) { cnt=0; dfs2(u,r); if(cnt>1 || self[u])dfs_ans(u); } vector <int> res; for(int i=0;i<n;i++)res.push_back(1-ans[i]); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...