Submission #707911

#TimeUsernameProblemLanguageResultExecution timeMemory
707911CyanmondToy Train (IOI17_train)C++17
22 / 100
2070 ms224980 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]); } int cntC = 0; int chargingS = -1; for (int i = 0; i < n; ++i) { if (r[i] == 1) { ++cntC; if (chargingS == -1) { chargingS = i; } } }/* if (cntC == 1) { // subtask 5 std::vector<int> reachableV(n, -1); reachableV[chargingS] = 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[chargingS] = -1; if (a[chargingS] == 1) { bool isOk = false; for (const int t : graph[chargingS]) { if (reachableV[t] == 1) { isOk = true; } else if (t == chargingS) { isOk = true; } } if (isOk) { reachableV[chargingS] = 1; } else { reachableV[chargingS] = 0; } } else { bool isOk = true; for (const int t : graph[chargingS]) { if (reachableV[t] == 0) { isOk = false; } } if (isOk) { reachableV[chargingS] = 1; } else { reachableV[chargingS] = 0; } } std::vector<int> answer(n); for (int i = 0; i < n; ++i) { answer[i] = (reachableV[i] == 1 and reachableV[chargingS] == 1) ? 1 : 0; } return answer; } else */if (std::all_of(a.begin(), a.end(), [](const int v) { return v == 0; })) { // subtask 4 std::vector<int> answer(n, 1); std::vector<bool> tCycle(n); for (int f = 0; f < n; ++f) { std::vector<int> type(n); auto dfs = [&](auto &&self, const int v) -> bool { type[v] = 1; for (const int t : graph[v]) { if (r[t] == 1) { continue; } if (type[t] == 0) { const auto res = self(self, t); if (res) { return true; } } else if (type[t] == 1) { return true; } } type[v] = 2; return false; }; tCycle[f] = dfs(dfs, f); } std::vector<std::vector<bool>> isReachable(n, std::vector<bool>(n)); for (int f = 0; f < n; ++f) { isReachable[f][f] = true; std::queue<int> que; que.push(f); while (not que.empty()) { const int x = que.front(); que.pop(); for (const int t : graph[x]) { if (not isReachable[f][t]) { isReachable[f][t] = true; que.push(t); } } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (isReachable[i][j] and tCycle[j]) { answer[i] = 0; } } } return answer; } else if (std::all_of(a.begin(), a.end(), [](const int v) { return v == 1; })) { // subtask 3 std::vector<int> answer(n); std::vector<bool> tCycle(n); for (int f = 0; f < n; ++f) { if (r[f] == 0) { continue; } std::vector<int> type(n); auto dfs = [&](auto &&self, const int v) -> bool { type[v] = 1; for (const int t : graph[v]) { if (type[t] == 0) { const auto res = self(self, t); if (res) { return true; } } else if (t == f) { return true; } } type[v] = 2; return false; }; tCycle[f] = dfs(dfs, f); } std::vector<std::vector<bool>> isReachable(n, std::vector<bool>(n)); for (int f = 0; f < n; ++f) { isReachable[f][f] = true; std::queue<int> que; que.push(f); while (not que.empty()) { const int x = que.front(); que.pop(); for (const int t : graph[x]) { if (not isReachable[f][t]) { isReachable[f][t] = true; que.push(t); } } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (isReachable[i][j] and tCycle[j]) { answer[i] = 1; } } } return answer; } else if (n <= 15) { // subtask 2 std::vector<int> pow3(n + 1); pow3[0] = 1; for (int i = 1; i <= n; ++i) { pow3[i] = pow3[i - 1] * 3; } std::vector<std::vector<char>> dp(n, std::vector<char>(pow3[n])); for (int bits = pow3[n] - 1; bits >= 0; --bits) { std::vector<int> status(n); for (int i = 0; i < n; ++i) { const int v = bits % pow3[i + 1]; const int c = v / pow3[i]; status[i] = c; } auto nextBits = [&](const int a) { assert(status[a] == 0); int res = bits; res += pow3[a]; if (r[a] == 1) { res += pow3[a]; for (int i = 0; i < n; ++i) { if (status[i] == 1) { res += pow3[i]; } } } return res; }; for (int f = 0; f < n; ++f) { if (status[f] == 0) { continue; } if (a[f] == 1) { bool isOk = false; for (const int t : graph[f]) { if (status[t] == 0) { isOk |= dp[t][nextBits(t)]; } else if (status[t] == 2) { isOk = true; } } dp[f][bits] = isOk; } else { bool isOk = true; for (const int t : graph[f]) { if (status[t] == 0) { if (not dp[t][nextBits(t)]) { isOk = false; } } else if (status[t] == 1) { isOk = false; } } dp[f][bits] = isOk; } } } std::vector<int> answer(n); for (int i = 0; i < n; ++i) { answer[i] = dp[i][pow3[i] * (r[i] + 1)] ? 1 : 0; } return answer; } else { // subtask 1 } }

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:8:42: warning: control reaches end of non-void function [-Wreturn-type]
    8 |     std::vector<std::vector<int>> graph(n);
      |                                          ^
#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...