Submission #707924

#TimeUsernameProblemLanguageResultExecution timeMemory
707924CyanmondToy Train (IOI17_train)C++17
39 / 100
962 ms224900 KiB
#include "train.h" #include <bits/stdc++.h> using namespace std; constexpr std::array<int, 16> pow3 = {{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907}}; 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> graphBit(n); for (int i = 0; i < n; ++i) { int b = 0; for (const int t : graph[i]) { b |= 1 << t; } graphBit[i] = b; } std::vector<std::vector<char>> dp(n, std::vector<char>(pow3[n])); for (int bits = pow3[n] - 1; bits >= 0; --bits) { static std::vector<int> status(n); int bit1 = 0, bit2 = 0, bit3 = 0, bit4 = 0; int qbits = bits; auto nextBits = [&](const int a) { int res = bits; res += pow3[a]; if (r[a] == 1) { res = qbits + 2 * pow3[a]; } return res; }; int bitsc = bits; for (int i = 0; i < n; ++i) { int cnt = 0; while (bitsc >= pow3[n - i - 1]) { bitsc -= pow3[n - i - 1]; ++cnt; } status[n - i - 1] = cnt; if (status[n - i - 1] == 1) { if (r[n - i - 1] == 1) { bitsc = -1; break; } qbits += pow3[n - i - 1]; } } if (bitsc == -1) continue; for (int i = 0; i < n; ++i) { const int c = status[i]; if (c == 1) { bit1 |= 1 << i; } else if (c == 2) { bit2 |= 1 << i; } else { if (dp[i][nextBits(i)]) { bit3 |= 1 << i; } else { bit4 |= 1 << i; } } } for (int f = 0; f < n; ++f) { if (status[f] == 0) { continue; } if (a[f] == 1) { bool isOk = false; isOk |= (bit2 && graphBit[f]); isOk |= (bit3 && graphBit[f]); dp[f][bits] = isOk; } else { bool isOk = true; if (bit1 && graphBit[f]) { isOk = false; } else if (bit4 && graphBit[f]) { 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 std::vector<int> answer(n); for (int i = 0; i < n; ++i) { int now = i; while (true) { if (a[now] == 1) { if (r[now] == 1 and std::find(graph[now].begin(), graph[now].end(), now) != graph[now].end()) { answer[i] = 1; break; } if (graph[now].size() == 1 and graph[now][0] == now) { answer[i] = 0; break; } ++now; } else { if (r[now] == 0 and std::find(graph[now].begin(), graph[now].end(), now) != graph[now].end()) { answer[i] = 0; break; } if (graph[now].size() == 1 and graph[now][0] == now) { answer[i] = 1; break; } ++now; } } } 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...