This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int N, M, timer, tin[5001], low[5001];
vector<int> adj[5001], G[5001], S;
bool vis[5001], self[5001], Scc[5001], ST[5001];
int DP[5001][5001];
void dfs(int v) {
tin[v] = low[v] = timer++;
vis[v] = 1; S.push_back(v);
for(auto u : G[v]) {
if(tin[u] == -1) dfs(u);
if(vis[u]) low[v] = min(low[v], low[u]);
}
if(tin[v] == low[v]) {
vector<int> V;
while(1) {
int U = S.back(); S.pop_back();
vis[U] = 0; V.push_back(U);
if(U == v) break;
}
if(V.size() == 1) return;
for(auto u : V) {
Scc[u] = 1;
}
}
}
int solve(int v, int t) {
if(Scc[v] || (self[v] && ST[v] == 0)) return 1;
if(DP[v][t] != -1) return DP[v][t];
if(t) {
for(auto u : adj[v]) {
if(solve(u, t - 1))
return DP[v][t] = 1;
}
}
if(ST[v] == 1 && adj[v].size() == 0)
return DP[v][t] = 0;
return DP[v][t] = 1;
}
vector<int> who_wins(vector<int> A, vector<int> R,
vector<int> U, vector<int> V) {
N = A.size(), M = U.size();
for(int l = 0; l < N; l++)
ST[l] = R[l];
for(int l = 0; l < M; l++) {
int X = U[l], Y = V[l];
if(X == Y) {
self[X] = 1;
if(ST[X] == 0) Scc[X] = 1;
continue;
}
adj[X].push_back(Y);
if(ST[X] == ST[Y] && ST[X] == 0)
G[X].push_back(Y);
}
memset(tin, -1, sizeof tin);
memset(DP, -1, sizeof DP);
for(int l = 0; l < N; l++) {
if(tin[l] != -1) continue;
dfs(l);
}
vector<int> res(N, 0);
for(int l = 0; l < N; l++) {
memset(vis, 0, sizeof vis);
res[l] = 1 - solve(l, N);
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |