Submission #707899

#TimeUsernameProblemLanguageResultExecution timeMemory
707899CyanmondToy Train (IOI17_train)C++17
0 / 100
2074 ms1416 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) { const int n = (int)a.size(), m = (int)u.size(); std::vector<std::vector<int>> graph(n); for (int i = 0; i < m; ++i) { graph[u[i]].push_back(v[i]); } auto calcReachability = [&](const int fin) { std::vector<int> reachableV(n, -1); reachableV[fin] = 1; for (int i = 0; i < n; ++i) { auto itr = std::find(graph[i].begin(), graph[i].end(), i); if (r[i] == 0 and a[i] == 0 and itr != graph[i].end()) { reachableV[i] = 0; } } for (int x = 0; x < 2 * n; ++x) { for (int i = 0; i < n; ++i) { if (reachableV[i] != -1) { continue; } if (a[i] == 1) { bool isOk = false, isRa = true; for (const int t : graph[i]) { if (reachableV[t] == 1) { isOk = true; } if (reachableV[t] == -1) { isRa = false; } } if (isOk) { reachableV[i] = 1; } else if (isRa) { reachableV[i] = 0; } } else { bool isOk = true, isRa = true; for (const int t : graph[i]) { if (reachableV[t] != 1) { isOk = false; } if (reachableV[t] == -1) { isRa = false; } } if (isOk) { reachableV[i] = 1; } else if (isRa) { reachableV[i] = 0; } } } } for (auto &e : reachableV) { if (e == -1) { e = 0; } } reachableV[fin] = -1; if (a[fin] == 1) { bool isOk = false; for (const int t : graph[fin]) { if (reachableV[t] == 1) { isOk = true; } else if (t == fin) { isOk = true; } } if (isOk) { reachableV[fin] = 1; } else { reachableV[fin] = 0; } } else { bool isOk = true; for (const int t : graph[fin]) { if (reachableV[t] == 0) { isOk = false; } } if (isOk) { reachableV[fin] = 1; } else { reachableV[fin] = 0; } } return reachableV; }; std::vector<std::vector<int>> reachability(n); for (int i = 0; i < n; ++i) { reachability[i] = calcReachability(i); } std::vector<int> answer(n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (r[j] == 1) { if (reachability[j][i] == 1 and reachability[j][j] == 1) { answer[i] = 1; } } } } 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...