Submission #584676

#TimeUsernameProblemLanguageResultExecution timeMemory
5846761neToy Train (IOI17_train)C++14
0 / 100
6 ms1492 KiB
#include "train.h" #include<bits/stdc++.h> using namespace std; std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { int n = (int)a.size(); int m = (int)u.size(); vector<int>ans(n); vector<vector<int>>adj(n); for (int i = 0;i<m;++i){ adj[u[i]].push_back(v[i]); } vector<bool>visited(n,false); int counts = 0; vector<int>dfs_initial(n,0); vector<int>dfs_low(n,0); vector<int>s; function<void(int)>dfs = [&](int u){ visited[u] = true; s.push_back(u); dfs_initial[u] = dfs_low[u] = ++counts; for (auto x:adj[u]){ if (!dfs_low[x]){ dfs(x); } if (visited[x]){ dfs_low[u] = min(dfs_low[u],dfs_low[x]); } } if (dfs_low[u] == dfs_initial[u]){ vector<int>temp; int got = 0; while(true){ int v = s.back(); s.pop_back(); visited[v] = false; temp.push_back(v); got|=r[v]; if (v==u)break; } if (got == 1){ for (auto x:temp){ ans[x] = got; } } } }; for (int i = 0;i<n;++i){ if (!dfs_low[i])dfs(i); } return ans; }
#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...