| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1323915 | Trisanu_Das | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int const N=2e5+10;
vector<int> adj[N] = {};
bool reach[N] = {};
bool bfs(int src,int dest,int l,int r) {
queue<pair<int,int> >Q;
Q.push({0, src});
reach[src] = 1;
while (Q.size()) {
int u, form;
tie(form, city) = Q.front(); Q.pop();
for (auto j : adj[u]) {
if (u < l && j > r) continue;
if (u > r && j < l) continue;
if (reach[j]) continue;
if (j > r && form == 1) continue;
if (j < l) Q.push({1, j});
else if (j > r) Q.push({0, j});
else Q.push({form,j});
reach[j] = 1;
}
}
return reach[dest];
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
for (int i = 0; i < X.size(); i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int>ans;
for (int i = 0; i < S.size(); i++) {
ans.push_back(bfs(S[i], E[i], L[i], R[i]));
for (int j = 0; j < N; j++) reach[j] = 0;
}
return ans;
}
