| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 868038 | vjudge1 | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int Q = L.size(), M = X.size();
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) adj[X[i]].emplace_back(Y[i]);
for (int i = 0; i < M; i++) adj[Y[i]].emplace_back(X[i]);
auto bfs = [&](int u, int l, int r) {
assert(l <= u && u <= r);
vector<int> done(N, 0);
done[u] = 1;
queue<int> q;
q.emplace(u);
while (q.size()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!done[v] && l <= v && v <= r) {
done[v] = 1;
q.emplace(v);
}
}
}
return done;
};
vector<int> A(Q);
for (int i = 0; i < Q; i++) {
auto ds = bfs(S[i], L[i], N);
auto de = bfs(E[i], 0, R[i]);
for (int j = 0; j < N; j++) {
if (de[j] && ds[j]) A[i] = 1;
}
}
return A;
}