Submission #838531

#TimeUsernameProblemLanguageResultExecution timeMemory
838531thimote75Toy Train (IOI17_train)C++14
5 / 100
1294 ms1620 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; using idata = vector<int>; using bdata = vector<bool>; using igrid = vector<idata>; idata controller, charger; int N, M; igrid roads; idata visited; int stage = 1; idata depth; bdata status; pair<int, bool> dfs (int node, int _depth) { if (visited[node] == stage) return { depth[node], status[node] }; depth [node] = _depth; status [node] = false; visited[node] = stage; int gdepth = controller[node] == 1 ? 1e9 : -1; bool rstatus = controller[node] == 0; for (int next : roads[node]) { pair<int, bool> ldata = dfs(next, _depth + 1); if (charger[node] && ldata.first <= depth[node]) ldata.second = true; if (controller[node] == 1) { gdepth = min(gdepth, ldata.first); rstatus |= ldata.second; } else { gdepth = max(gdepth, ldata.first); rstatus &= ldata.second; } } status[node] = rstatus; return { gdepth, rstatus }; } idata who_wins(idata _controller, idata _charger, idata u, idata v) { N = _controller.size(); M = u.size(); controller = _controller; charger = _charger; roads.resize(N); for (int i = 0; i < M; i ++) roads[u[i]].push_back(v[i]); visited.resize(N); depth .resize(N); status.resize(N); idata answer(N, false); for (int i = 0; i < N; i ++) { answer[i] = dfs(i, 0).second; stage ++; } return answer; }
#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...