Submission #239495

#TimeUsernameProblemLanguageResultExecution timeMemory
239495JatanaToy Train (IOI17_train)C++17
100 / 100
593 ms1792 KiB
#include "train.h" #include <iostream> #include <numeric> #define le(v) ((int)v.size()) #define x first #define y second #define pb push_back #define f(i, n) for (int i = 0; i < (n); i++) using namespace std; int n, m; vector<int> who; vector<vector<int>> g; vector<vector<int>> reg; vector<int> c; vector<int> ic; vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { g.clear(); c.clear(); who.clear(); who = a; n = le(a); m = le(u); ic = c = r; g.resize(n); reg.resize(n); // cerr <<n << endl; // f(i, m) { // cerr << u[i] << " " << v[i] << endl; // } // return c; f(i, m) { g[u[i]].pb(v[i]); reg[v[i]].pb(u[i]); } vector<bool> dead(n, false); while (true) { f(i, n) { if (dead[i]) { c[i] = 0; } else c[i] = ic[i]; } { vector<int> deq(n); iota(deq.begin(), deq.end(), 0); while (!deq.empty()) { int i = deq.back(); deq.pop_back(); if (dead[i]) continue; if (c[i] == 1) continue; if (who[i] == 1) { // indefinitely for (int sub : g[i]) { if (c[sub]) { c[i] = 1; break; } } } else { // finitely bool some = false; for (int sub : g[i]) { if (!c[sub]) { some = true; break; } } if (!some) { c[i] = 1; } } if (c[i] == 1) { for (int sub : reg[i]) { deq.pb(sub); } } } } while (true) { vector<int> was = c; for (int i = 0; i < n; i++) { if (dead[i]) continue; if (c[i] == 0) continue; if (who[i] == 1) { // indefinitely bool some = false; for (int sub : g[i]) { if (c[sub]) { some = true; break; } } if (!some) { c[i] = 0; } } else { // finitely for (int sub : g[i]) { if (!c[sub]) { c[i] = 0; break; } } } } if (was == c) break; } bool _new = false; f(i, n) { if (!c[i]) { if (!dead[i]) _new = true; dead[i] = true; } } if (!_new) break; } vector<int> out(n); f(i, n) { if (dead[i]) { out[i] = 0; } else out[i] = 1; } return out; // vector<int> res(a.size()); // for(int i = 0; i < (int)res.size(); i++) // res[i] = i % 2; // return res; }
#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...