// #include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long
// #define int long long
// #define int unsigned long long
const ll inf = 1e9 + 7;
const ll weirdMod = 998244353;
const int maxN = 2e5 + 15;
const int lg = 21;
// namespace {
// int read_int() {
// int x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
// }
// } // namespace
vector<int> g[maxN], adj[maxN][2], vc; vector<pair<pii, pii>> qs[maxN];
int n, par[maxN][2], p[maxN][lg][2], in[maxN][2], out[maxN][2], tim, t[4 * maxN];
void update(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
t[v] = val;
return;
} int tm = (tl + tr) / 2;
if (pos <= tm) update(2 * v, tl, tm, pos, val);
else update(2 * v + 1, tm + 1, tr, pos, val);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
int getmax(int v, int tl, int tr, int l, int r) {
if (l > r) return -inf;
if (tl == l && tr == r) return t[v];
int tm = (tl + tr) / 2;
return max(getmax(2 * v, tl, tm, l, min(r, tm)),
getmax(2 * v + 1, tm + 1, tr, max(l, tm + 1), tr));
}
void make_set() {
for (int i = 1; i <= n; i++) {
par[i][0] = par[i][1] = i;
p[i][0][0] = p[i][0][1] = i;
}
}
int find_set(int v, int f) {
if (par[v][f] == v)
return v;
return par[v][f] = find_set(par[v][f], f);
}
void union_set(int x, int y, int f) {
int rx = find_set(x, f), ry = find_set(y, f);
if (rx != ry) {
par[ry][f] = rx;
p[ry][0][f] = x;
}
}
void dfs(int v, int f) {
if (f) vc.pb(v);
in[v][f] = ++tim;
for (int u : adj[v][f]) dfs(u, f);
out[v][f] = tim;
}
int left_lift(int val, int x) {
for (int i = lg - 1; i >= 0; i--)
if (p[x][i][1] >= val) x = p[x][i][1];
return x;
}
int right_lift(int val, int x) {
for (int i = lg - 1; i >= 0; i--)
if (p[x][i][0] <= val) x = p[x][i][0];
return x;
}
vector<int> check_validity(int _n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
n = _n;
for (int i = 0; i < x.size(); i++) {
x[i]++; y[i]++;
g[x[i]].pb(y[i]);
g[y[i]].pb(x[i]);
} make_set();
for (int i = 1; i <= n; i++)
for (int j : g[i]) if (j < i) union_set(i, j, 0);
for (int i = n; i >= 1; i--)
for (int j : g[i]) if (j > i) union_set(i, j, 1);
for (int i = 1; i <= n; i++) {
if (p[i][0][0] != i) adj[p[i][0][0]][0].pb(i);
if (p[i][0][1] != i) adj[p[i][0][1]][1].pb(i);
} for (int i = 1; i < lg; i++) {
for (int j = 1; j <= n; j++) {
p[j][i][0] = p[p[j][i - 1][0]][i - 1][0];
p[j][i][1] = p[p[j][i - 1][1]][i - 1][1];
}
} dfs(n, 0); tim = 0; dfs(1, 1);
vector<int> ans; ans.resize(s.size());
for (int i = 0; i < s.size(); i++) {
s[i]++; e[i]++; l[i]++; r[i]++;
int rl = left_lift(l[i], s[i]);
int rr = right_lift(r[i], e[i]);
qs[out[rl][1]].pb({{i, in[rl][1]}, {in[rr][0], out[rr][0]}});
} for (int i = 1; i <= n; i++) {
update(1, 1, n, in[vc[i - 1]][0], i);
for (auto v : qs[i]) {
ans[v.ff.ff] = (getmax(1, 1, n, v.sc.ff, v.sc.sc) >= v.ff.sc);
}
} return ans;
}
// int main() {
// int N = read_int();
// int M = read_int();
// int Q = read_int();
// std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
// for (int j = 0; j < M; ++j) {
// X[j] = read_int();
// Y[j] = read_int();
// }
// for (int i = 0; i < Q; ++i) {
// S[i] = read_int();
// E[i] = read_int();
// L[i] = read_int();
// R[i] = read_int();
// }
// std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
// for (size_t i = 0; i < A.size(); ++i) {
// printf("%d\n", A[i]);
// }
// return 0;
// }
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
werewolf.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
19292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
19292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
402 ms |
97648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
19292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
