#include <bits/stdc++.h>
using namespace std;
int N, M, P[5001];
int timer, tin[5001], low[5001];
vector<int> adj[5001], G[5001], S;
bool vis[5001], self[5001], Scc[5001], ST[5001];
int station, reach[5001], DP[5001][5001];
int findSet(int v) {
if(P[v] == v) return v;
return P[v] = findSet(P[v]);
}
bool sameSet(int u, int v) {
return findSet(u) == findSet(v);
}
void unionSet(int u, int v) {
u = findSet(u), v = findSet(v);
if(u == v) return;
P[u] = v;
}
void dfs(int v) {
tin[v] = low[v] = timer++;
vis[v] = 1; S.push_back(v);
for(auto u : adj[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(int l = 1; l < V.size(); l++) {
unionSet(V[l], V[l - 1]);
}
}
}
int solve(int v, int t, int c, vector<int> A) {
if(!reach[v]) return DP[v][t] = 0;
if(DP[v][t] != -1) return DP[v][t];
if(ST[v]) t = N;
if(DP[v][t] != -1) return DP[v][t];
if(v == station) c++;
if(c == 2) return DP[v][t] = 1;
if(t == 0) return DP[v][t] = 0;
if(A[v] == 1) {
if(self[v] && ST[v])
return DP[v][t] = 1;
for(auto u : adj[v]) {
if(solve(u, t - 1, c, A))
return DP[v][t] = 1;
}
return DP[v][t] = 0;
}
if(A[v] == 0) {
if(self[v] && !ST[v])
return DP[v][t] = 0;
for(auto u : adj[v]) {
if(solve(u, t - 1, c, A) == 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], P[l] = l;
station = (ST[l] == 1 ? l : station);
}
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);
G[Y].push_back(X);
}
memset(tin, -1, sizeof tin);
memset(DP, -1, sizeof DP);
for(int l = 0; l < N; l++) {
if(tin[l] != -1) continue;
dfs(l);
}
queue<pair<int, int>> q;
vector<int> D(N, 1e9 + 7);
q.push({station, 0}); D[station] = 0;
while(!q.empty()) {
int X = q.front().first;
q.pop(); reach[X] = 1;
for(auto Y : G[X]) {
if(D[X] + 1 < D[Y]) {
D[Y] = D[X] + 1;
q.push({Y, D[Y]});
}
}
}
vector<int> res(N);
for(int l = 0; l < N; l++)
res[l] = solve(l, N, 0, A);
return res;
}
Compilation message
train.cpp: In function 'void dfs(int)':
train.cpp:39:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int l = 1; l < V.size(); l++) {
| ~~^~~~~~~~~~
train.cpp: In function 'int solve(int, int, int, std::vector<int>)':
train.cpp:70:9: warning: control reaches end of non-void function [-Wreturn-type]
70 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
100336 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
99796 KB |
3rd lines differ - on the 11th token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
126 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
237772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
105 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2080 ms |
198196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
100336 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
99796 KB |
3rd lines differ - on the 11th token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
