# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1016337 | lacito | Werewolf (IOI18_werewolf) | C++14 | 4062 ms | 27988 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.
#include "werewolf.h"
using namespace std;
const int MAXN = 3000;
vector<int> g[MAXN];
vector<bool> vis;
int n, l, r;
void dfs(int v, bool human) {
vis[v] = true;
for (int u : g[v]) {
if (!vis[u]) {
if (human && u >= l || !human && u <= r) { // werewolf condition
dfs(u, human);
}
}
}
}
int solve(int s, int e) {
// check all the cities where we can transform
for (int i = l; i <= r; i++) {
vis.assign(n, false);
dfs(i, true);
if (vis[s]) {
vis.assign(n, false);
dfs(i, false);
if (vis[e]) return 1;
}
}
return 0;
}
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++) {
// road between X[i] and Y[i]
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
n = N;
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
l = L[i];
r = R[i];
A[i] = solve(S[i], E[i]);
}
return A;
}
Compilation message (stderr)
# | 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... |