제출 #68950

#제출 시각아이디문제언어결과실행 시간메모리
68950aquablitz11장난감 기차 (IOI17_train)C++14
15 / 100
2075 ms92076 KiB
#include <bits/stdc++.h> #include "train.h" using namespace std; using pii = pair<int, int>; const int N = 5e3+10; int n, m; vector<int> G[N], R[N]; vector<int> A, C; bool can[N][N]; int cnt[N][N], need[N]; vector<int> who_wins(vector<int> AA, vector<int> CC, vector<int> U, vector<int> V) { swap(AA, A), swap(CC, C); // input n = A.size(); m = U.size(); for (int i = 0; i < m; ++i) { G[U[i]].push_back(V[i]); R[V[i]].push_back(U[i]); } // find reachable states queue<pii> Q; for (int i = 0; i < n; ++i) { need[i] = A[i] ? (int)G[i].size() : 1; can[i][n] = true; Q.emplace(i, n); } while (!Q.empty()) { int u = Q.front().first, p = Q.front().second; Q.pop(); for (auto v : G[u]) { int np = C[v] ? n : p-1; if (!can[v][np] && p >= 1) { can[v][np] = true; Q.emplace(v, np); } } } // winning position vector<int> ans(n, 1); for (int i = 0; i < n; ++i) if (can[i][0]) Q.emplace(i, 0), can[i][0] = false; while (!Q.empty()) { int u = Q.front().first, p = Q.front().second; Q.pop(); if (p == n) ans[u] = 0; int pl = 1, pr = n; if (!C[u]) pl = pr = p+1; for (auto v : R[u]) { for (int np = pl; np <= pr && np <= n; ++np) { if (can[v][np] && ++cnt[v][np] == need[v]) { can[v][np] = false; Q.emplace(v, np); } } } } 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...