Submission #72858

#TimeUsernameProblemLanguageResultExecution timeMemory
72858Sa1378Toy Train (IOI17_train)C++17
0 / 100
23 ms3880 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],flg; vector <int> e[N],er[N],tpl; void dfs(int x) { mark[x]=1; for(auto u:e[x]) if(!mark[u]) dfs(u); tpl.push_back(x); } void dfs2(int x,vector <int> &r) { mark[x]=1; cnt++;flg|=r[x]; 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<m;i++) if(!mark[i]) dfs(i); reverse(tpl.begin(),tpl.end()); memset(mark,0,sizeof mark); for(auto u:tpl) if(!mark[u]) { flg=0;cnt=0; dfs2(u,r); if(flg && (cnt>1 || self[u]))dfs_ans(u); } vector <int> res; for(int i=0;i<n;i++)res.push_back(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...