Submission #669797

#TimeUsernameProblemLanguageResultExecution timeMemory
669797someoneToy Train (IOI17_train)C++14
100 / 100
267 ms1532 KiB
//#include "train.h" #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 42, INF = 1e9; int n, m, nb[N], nbS[N]; vector<int> adj[N], ans; bool isA[N], isR[N], sent[N], mod[N]; void dfs(int i) { if(sent[i]) return; sent[i] = true; for(int j : adj[i]) { nbS[j]++; if(isA[j] || nbS[j] == nb[j]) dfs(j); } } vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { n = (int)a.size(); m = (int)u.size(); for(int i = 0; i < n; i++) isA[i] = (a[i] == 1), isR[i] = (r[i] == 1); for(int i = 0; i < m; i++) { nb[u[i]]++; adj[v[i]].push_back(u[i]); } deque<int> id; for(int i = 0; i < n; i++) if(r[i]) id.push_back(i); int sz = (int)id.size(); while(true) { for(int i : id) dfs(i); for(int i = 0; i < sz; i++) { if((isA[id[0]] && nbS[id[0]] > 0) || nbS[id[0]] == nb[id[0]]) id.push_back(id[0]); id.pop_front(); } for(int i = 0; i < n; i++) { nbS[i] = 0; sent[i] = false; } if(sz == (int)id.size()) break; sz = id.size(); } for(int i : id) dfs(i); for(int i = 0; i < n; i++) ans.push_back(sent[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...