Submission #584680

#TimeUsernameProblemLanguageResultExecution timeMemory
5846801neToy Train (IOI17_train)C++14
0 / 100
6 ms1004 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,0); vector<int>cnt(n,0); vector<int>parent(n,-1); for (int i = 0;i<n;++i){ function<int(int)>dfs = [&](int u){ if (visited[u]){ int x = u; int got = 0; while(parent[x]!=u && parent[x]!=-1){ got|=r[x]; x = parent[x]; } x = parent[x]; if (x == u){ return (got | cnt[u]); } return cnt[u]; } visited[u] = true; int ans = 0; for (auto x:adj[u]){ parent[x] = u; ans|=dfs(x); } return cnt[u] = ans; }; if (visited[i] != -1){ ans[i] = cnt[i]; } else{ ans[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...