제출 #68318

#제출 시각아이디문제언어결과실행 시간메모리
68318aquablitz11장난감 기차 (IOI17_train)C++14
15 / 100
2065 ms126636 KiB
#include <bits/stdc++.h> #include "train.h" using namespace std; using pii = pair<int, int>; const int N = 5e3+10; int n, m; int deg[N]; vector<int> R[N]; bool used[N][N]; int cnt[N][N]; vector<int> who_wins(vector<int> A, vector<int> C, vector<int> U, vector<int> V) { // input n = A.size(); m = U.size(); for (int i = 0; i < m; ++i) { ++deg[U[i]]; R[V[i]].push_back(U[i]); } // winning position for B queue<int> Q; for (int i = 0; i < n; ++i) { used[i][0] = true; Q.push(i*(n+1)+0); } vector<int> ans(n, 1); while (!Q.empty()) { int valu = Q.front(); int u = valu/(n+1), p = valu%(n+1); Q.pop(); if (p == n) ans[u] = 0; if (!C[u] && p+1 <= n) for (auto v : R[u]) { int np = p+1; if (C[v] && np != n) continue; ++cnt[v][np]; if (cnt[v][np] == (A[v] ? (int)deg[v] : 1) && !used[v][np]) { used[v][np] = true; Q.push(v*(n+1)+np); } } if (C[u] && p == n) for (auto v : R[u]) { if (C[v]) { int np = n; ++cnt[v][np]; if (cnt[v][np] == (A[v] ? (int)deg[v] : 1) && !used[v][np]) { used[v][np] = true; Q.push(v*(n+1)+np); } } else for (int np = 1; np <= n; ++np) { ++cnt[v][np]; if (cnt[v][np] == (A[v] ? (int)deg[v] : 1) && !used[v][np]) { used[v][np] = true; Q.push(v*(n+1)+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...