Submission #536340

#TimeUsernameProblemLanguageResultExecution timeMemory
536340skittles1412Toy Train (IOI17_train)C++17
100 / 100
501 ms1364 KiB
#include "bits/extc++.h" using namespace std; template <typename T> void dbgh(const T& t) { cerr << t << endl; } template <typename T, typename... U> void dbgh(const T& t, const U&... u) { cerr << t << " | "; dbgh(u...); } #ifdef DEBUG #define dbg(...) \ cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \ << ": "; \ dbgh(__VA_ARGS__) #else #define cerr \ if (false) \ cerr #define dbg(...) 1412 #endif #define endl "\n" #define long int64_t #define sz(x) int((x).size()) const int maxn = 5000; int n, m; bool vis[maxn]; vector<int> own, dep, igraph[maxn]; vector<int> reachable(const vector<int>& arr, int side) { vector<int> dep = ::dep; bool qd[n]{}; vector<int> q; auto push = [&](int u, bool f = false) -> void { if (!qd[u] && (f || !dep[u])) { qd[u] = true; q.push_back(u); } }; for (int i = 0; i < n; i++) { if (!vis[i] && arr[i]) { push(i, true); } } vector<int> ans(n); while (sz(q)) { int u = q.back(); q.pop_back(); ans[u] = true; for (auto& v : igraph[u]) { if (!vis[v]) { dep[v]--; if (own[v] == side) { push(v, true); } else { push(v); } } } } return ans; } vector<int> who_wins(vector<int> own, vector<int> charging, vector<int> us, vector<int> vs) { ::own = own; n = sz(own); m = sz(us); for (int i = 0; i < m; i++) { int u = us[i], v = vs[i]; igraph[v].push_back(u); } dep.resize(n); for (auto& a : us) { dep[a]++; } while (true) { vector<int> cur = reachable(charging, 1); for (auto& a : cur) { a ^= 1; } vector<int> nxt = reachable(cur, 0); int sz = 0; for (int i = 0; i < n; i++) { if (nxt[i]) { vis[i] = true; for (int j = 0; j < m; j++) { if (i == vs[j]) { dep[us[j]]--; } } sz++; } } if (!sz) { break; } } return reachable(charging, 1); }
#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...