#include "train.h"
//author: erray
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/debug.h"
#else
#define debug(...) (void) 37
#endif
std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> U, std::vector<int> V) {
int N = int(A.size());
int M = int(U.size());
vector<vector<int>> rg(N);
vector<int> outdeg_def(N);
for (int i = 0; i < M; ++i) {
rg[V[i]].push_back(U[i]);
outdeg_def[U[i]] += 1;
}
while (true) {
debug(R);
auto Expand = [&](vector<int> que, int side) {
auto outdeg = outdeg_def;
vector<bool> vis(N);
for (auto v : que) {
vis[v] = true;
}
for (int it = 0; it < int(que.size()); ++it) {
int v = que[it];
for (auto u : rg[v]) {
if (!vis[u] && (A[u] == side || --outdeg[u] == 0)) {
que.push_back(u);
vis[u] = true;
}
}
}
return vis;
};
vector<int> stats;
for (int i = 0; i < N; ++i) {
if (R[i]) {
stats.push_back(i);
}
}
auto inv = Expand(stats, 1);
vector<int> ends;
for (int i = 0; i < N; ++i) {
if (!inv[i]) {
ends.push_back(i);
}
}
auto new_R = Expand(ends, 0);
bool change = false;
for (int i = 0; i < N; ++i) {
change |= R[i] == new_R[i];
R[i] = !new_R[i];
}
if (!change) {
break;
}
}
return R;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
852 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Incorrect |
0 ms |
300 KB |
3rd lines differ - on the 4th token, expected: '0', found: '1' |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
1340 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1080 KB |
Output is correct |
2 |
Correct |
5 ms |
1204 KB |
Output is correct |
3 |
Correct |
5 ms |
1236 KB |
Output is correct |
4 |
Correct |
6 ms |
1340 KB |
Output is correct |
5 |
Correct |
7 ms |
1236 KB |
Output is correct |
6 |
Correct |
5 ms |
1236 KB |
Output is correct |
7 |
Correct |
5 ms |
1236 KB |
Output is correct |
8 |
Correct |
7 ms |
1236 KB |
Output is correct |
9 |
Correct |
5 ms |
1204 KB |
Output is correct |
10 |
Correct |
5 ms |
1236 KB |
Output is correct |
11 |
Correct |
5 ms |
1364 KB |
Output is correct |
12 |
Correct |
7 ms |
1236 KB |
Output is correct |
13 |
Correct |
5 ms |
1212 KB |
Output is correct |
14 |
Correct |
5 ms |
1236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
1236 KB |
Output is correct |
2 |
Correct |
5 ms |
1236 KB |
Output is correct |
3 |
Correct |
5 ms |
1236 KB |
Output is correct |
4 |
Correct |
5 ms |
1236 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
852 KB |
Output is correct |
7 |
Correct |
3 ms |
852 KB |
Output is correct |
8 |
Incorrect |
3 ms |
852 KB |
3rd lines differ - on the 5th token, expected: '0', found: '1' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
852 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |