#include <bits/stdc++.h>
using namespace std;
vector<int> who_wins(vector<int> own, vector<int> rs, vector<int> us, vector<int> vs) {
int n = own.size();
vector<vector<int>> G(n);
for (int i = 0; i < us.size(); ++i) {
G[us[i]].push_back(vs[i]);
}
//marc[i] = 1 if starting from vertex i it i spossible to reach any vertex in ss regardless of the opponents moves
auto reach = [&](vector<bool> &ss) {
vector<bool> marc = ss;
queue<int> q;
for (int i = 0; i < n; ++i)
if (marc[i]) q.push(i);
vector<int> in(n);
for (int i = 0; i < n; ++i)
if (!own[i]) in[i] = G[i].size();
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v: G[u]) if (!marc[v])
if (own[v]) { marc[v] = true; q.push(v); }
else { --in[v]; if (in[v] == 0) { marc[v] = true; q.push(v); }}
}
return marc;
};
//current set of verticies to check
vector<bool> rline(rs.begin(), rs.end());
bool change = true;
while (true) {
vector<bool> fs = reach(rline);
change = false;
for (int u = 0; u < n; ++u) {
if (!rline[u]) continue;
if (own[u]) {
bool ok = false;
for (int v: G[u]) {
if (fs[v]) ok = true;
}
if (!ok) {
rline[u] = false;
change = true;
}
}
else {
bool ok = true;
for (int v: G[u]){
if (!fs[v]) ok = false;
}
if (!ok) {
rline[u] = false;
change = true;
}
}
}
}
auto ans = reach(rline);
return vector<int>(ans.begin(), ans.end());
}
# | 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... |