Submission #1025461

#TimeUsernameProblemLanguageResultExecution timeMemory
1025461shiomusubi496Toy Train (IOI17_train)C++17
23 / 100
809 ms2068 KiB
#include "train.h" #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i) #define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i) #define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i) #define all(v) begin(v), end(v) using namespace std; template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; } template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; } using ll = long long; std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { vector<int> ids(a.size()); iota(all(ids), 0); vector<int> ans(a.size()); while (true) { int n = a.size(), m = u.size(); vector<vector<int>> g(n), rg(n); rep (i, m) { g[u[i]].push_back(v[i]); rg[v[i]].push_back(u[i]); } auto calc = [&](vector<int> r, bool f) -> vector<int> { queue<int> que; rep (i, n) { if (r[i]) que.push(i); } vector<int> deg(n); rep (i, n) deg[i] = g[i].size(); while (!que.empty()) { int i = que.front(); que.pop(); for (int j : rg[i]) { if (r[j]) continue; if (a[j] == f) { r[j] = true; } else { if ((--deg[j]) == 0) { r[j] = true; } } if (r[j]) que.push(j); } } return r; }; auto r2 = calc(r, 1); if (count(all(r2), 1) == n) { rep (i, n) ans[ids[i]] = 1; break; } rep (i, n) r2[i] ^= 1; auto r3 = calc(r2, 0); vector<int> idx(n, -1); vector<int> ids2; int cnt = 0; rep (i, n) { if (!r3[i]) { idx[i] = cnt++; ids2.push_back(i); } } vector<int> a2(cnt), r4(cnt); rep (i, n) { if (idx[i] == -1) continue; a2[idx[i]] = a[i]; r4[idx[i]] = r[i]; } vector<int> u2, v2; rep (i, m) { if (idx[u[i]] == -1 || idx[v[i]] == -1) continue; u2.push_back(idx[u[i]]); v2.push_back(idx[v[i]]); } rep (i, n) { if (idx[i] == -1) ans[ids[i]] = 0; } a = a2; r = r4; u = u2; v = v2; ids = ids2; } 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...