#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) (int)x.size()
using namespace std;
using VI = vector <int>;
using PII = pair <int, int>;
const int N = 2e5+1;
const int M = (1<<19)+1;
int n, m, q;
vector <int> paths[N];
int ans[N], p[N];
VI nums, res;
struct Node {
int mn, mx;
} node[M];
void build(int l, int r, int head) {
if (l == r) {
node[head] = {nums[l], nums[l]};
return;
}
int mid = (l+r)>>1;
build(l, mid, head*2+1);
build(mid+1, r, head*2+2);
node[head] = {min(node[head*2+1].mn, node[head*2+2].mn), max(node[head*2+1].mx, node[head*2+2].mx)};
}
void dfs(int pos, int par = -1) {
// cout << pos << " ";
p[pos] = sz(nums);
nums.pb(pos);
for (auto el : paths[pos]) {
if (el == par) continue;
dfs(el, pos);
}
}
int middle(PII a, int b) {
return (a.ff <= b && b <= a.ss);
}
PII zero = {1e9, -1e9};
PII merge(PII a, PII b, int l, int r, int pos) {
if (a == zero) a = b;
if (b == zero) b = a;
if (a == b && b == zero) return zero;
if (a.ss+1 == b.ff) {
a.ss = b.ss;
if (middle(a, pos)) return a;
if (r < pos && a.ss == r) return a;
if (pos < l && a.ff == l) return a;
return zero;
}
if (middle(mp(l, r), pos)) {
if (middle(a, pos)) return a;
if (middle(b, pos)) return b;
return zero;
}
if (r < pos) {
if (b.ss == r) return b;
return zero;
}
// pos < l
if (a.ff == l) return a;
return zero;
}
PII getBoundaryA(int l, int r, int pos, int lim, int head) { // human
if (node[head].mx < lim) return zero;
if (node[head].mn >= lim) return {l, r};
int mid = (l+r)>>1;
PII a = getBoundaryA(l, mid, pos, lim, head*2+1);
PII b = getBoundaryA(mid+1, r, pos, lim, head*2+2);
return merge(a, b, l, r, pos);
}
PII getBoundaryB(int l, int r, int pos, int lim, int head) { // wolf
if (node[head].mn > lim) {
PII c = zero;
return zero;
}
if (node[head].mx <= lim) {
PII c = {l, r};
return {l, r};
}
int mid = (l+r)>>1;
PII a = getBoundaryB(l, mid, pos, lim, head*2+1);
PII b = getBoundaryB(mid+1, r, pos, lim, head*2+2);
PII c = merge(a, b, l, r, pos);
return merge(a, b, l, r, pos);
}
bool intersect(PII a, PII b) {
int x = a.ss - a.ff + 1;
int y = b.ss - b.ff + 1;
int l = min(a.ff, b.ff);
int r = min(a.ss, b.ss);
l = r - l + 1;
return (x+y > l);
}
VI check_validity(int _N, VI X, VI Y, VI ST, VI ED, VI L, VI R) {
n = _N;
m = sz(X);
q = sz(ST);
for (int i = 0; i < m; i++) {
paths[X[i]].pb(Y[i]);
paths[Y[i]].pb(X[i]);
}
int st = 0;
while(sz(paths[st]) != 1) st++;
dfs(st);
// cout << "\n";
build(0, n-1, 0);
for (int i = 0; i < q; i++) {
PII a = getBoundaryA(0, n-1, p[ST[i]], L[i], 0);
PII b = getBoundaryB(0, n-1, p[ED[i]], R[i], 0);
// cout << a.ff << ' ' << a.ss << ' ';
// cout << b.ff << ' ' << b.ss << '\n';
res.pb(intersect(a, b));
}
return res;
}
Compilation message
werewolf.cpp: In function 'PII getBoundaryB(int, int, int, int, int)':
werewolf.cpp:78:13: warning: variable 'c' set but not used [-Wunused-but-set-variable]
78 | PII c = zero;
| ^
werewolf.cpp:82:13: warning: variable 'c' set but not used [-Wunused-but-set-variable]
82 | PII c = {l, r};
| ^
werewolf.cpp:88:9: warning: variable 'c' set but not used [-Wunused-but-set-variable]
88 | PII c = merge(a, b, l, r, pos);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
338 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
338 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4033 ms |
35868 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
338 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
