| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 295861 | SeDunion | 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.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5;
vector<int>vec,g[MAXN];
int pos[MAXN];
int mn[MAXN << 2], mx[MAXN << 2];
void dfs (int v, int p = -1) {
vec.push_back (v);
for (int to : g[v]) if (to != p) dfs (to, v);
}
void build (int l = 0, int r = vec.size(), int v = 0) {
if (r - l == 1) { mn[v] = mx[v] = vec[l]; return; }
int m = (l + r) >> 1;
build (l, m, v + v + 1), build (m, r, v + v + 2);
mn[v] = min (mn[v + v + 1], mn[v + v + 2]);
mx[v] = max (mx[v + v + 1], mx[v + v + 2]);
}
int getmn (int L, int R, int l = 0, int r = vec.size(), int v = 0) {
if (L <= l && r <= R) return mn[v];
if (L >= r || l >= R) return MAXN;
int m = (l + r) >> 1;
return min (getmn (L, R, l, m, v + v + 1), getmn (L, R, m, r, v + v + 2));
}
int getmx (int L, int R, int l = 0, int r = vec.size(), int v = 0) {
if (L <= l && r <= R) return mx[v];
if (L >= r || l >= R) return -MAXN;
int m = (l + r) >> 1;
return max (getmx (L, R, l, m, v + v + 1), getmx (L, R, m, r, v + v + 2));
}
vector<int> check_validity
(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int M = X.size();
for (int i = 0 ; i < M ; ++ i) {
g[X[i]].push_back (Y[i]);
g[Y[i]].push_back (X[i]);
}
int root;
for (int i = 0 ; i < N ; ++ i) {
if (g[i].size() == 1) root = i;
}
dfs(root);
build();
for (int i = 0 ; i < N ; ++ i) {
pos[vec[i]] = i;
}
int Q = S.size();
vector<int>ans(Q);
for (int i = 0 ; i < Q ; ++ i) {
int s = S[i], e = E[i];
int l = pos[s], r = pos[e], res = 0;
for (int v = l ; v <= r ; ++ v) {
if (getmn (l, m + 1) >= L[i] && getmx (m, r + 1) <= R[i]) { res = 1; break; }
}
// while (l <= r) {
// int m = (l + r) >> 1;
// bool lf = (getmn (pos[s], m + 1) >= L[i]);
// bool rg = (getmx (m, pos[e] + 1) <= R[i]);
// if (lf && rg) {
// res = 1;
// break;
// }
// if (!lf) r = m - 1;
// else l = m + 1;
// }
ans[i] = res;
}
return ans;
}