이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "train.h"
using namespace std;
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
typedef vector<int> vi;
vi who_wins(vi a, vi r, vi u, vi v) {
int n = a.size();
int m = u.size();
int L, R;
vector<vi> adj(n);
vi d(n), cnt(n);
rep(i, 0, m) {
adj[v[i]].pb(u[i]);
d[u[i]]++;
}
vector<bool> dead(n);
vi q(n);
while (true) {
fill(all(dead), true);
fill(all(cnt), 0);
L = R = 0;
rep(i, 0, n) if (r[i]) {
dead[i] = false;
q[R++] = i;
}
while (L < R) {
int me = q[L++];
for (auto e : adj[me]) {
if (!dead[e]) continue;
cnt[e]++;
if (a[e] || cnt[e] == d[e]) {
dead[e] = false;
q[R++] = e;
}
}
}
L = R = 0;
fill(all(cnt), 0);
rep(i, 0, m) if (dead[v[i]]) cnt[u[i]]++;
rep(i, 0, n) if (cnt[i] && (!a[i] || cnt[i] == d[i])) {
dead[i] = true;
q[R++] = i;
}
while (L < R) {
int me = q[L++];
for (auto e : adj[me]) {
if (dead[e]) continue;
cnt[e]++;
if (!a[e] || cnt[e] == d[e]) {
dead[e] = true;
q[R++] = e;
}
}
}
bool flag = false;
rep(i, 0, n) if (dead[i] && r[i]) {
flag = true;
r[i] = 0;
}
if (!flag) break;
}
fill(all(dead), true);
fill(all(cnt), 0);
L = R = 0;
rep(i, 0, n) if (r[i]) {
dead[i] = false;
q[R++] = i;
}
while (L < R) {
int me = q[L++];
for (auto e : adj[me]) {
if (!dead[e]) continue;
cnt[e]++;
if (a[e] || cnt[e] == d[e]) {
dead[e] = false;
q[R++] = e;
}
}
}
vi res(n);
rep(i, 0, n) if (!dead[i]) res[i] = 1;
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... |