#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
template<typename T>
int len(T &a){return a.size();}
const int inf = 1e9 + 10;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct DSU{
vector<int> par, sz; int n;
DSU (int _n){
n = _n;
par.resize(n);
iota(all(par), 0);
sz.assign(n, 1);
}
DSU (){}
int get(int a){
return (par[a] == a ? a : par[a] = get(par[a]));
}
void init(int _n){
n = _n;
par.resize(n);
iota(all(par), 0);
sz.assign(n, 1);
}
void unite(int a, int b){
a = get(a);
b = get(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a,b);
sz[a] += sz[b];
par[b] = a;
}
void link(int a, int b){
a = get(a); b = get(b);
if(a == b) return;
sz[b] += sz[a];
par[a] = b;
}
};
int n, m, q;
vector<vector<int>> g;
vector<int> line;
void dfs(int i, int p = -1){
line.push_back(i);
for(auto u : g[i]){
if(u != p) dfs(u, i);
}
}
struct Sparsemin{
int n, logn;
vector<vector<int>> t;
Sparsemin (){}
void init(int _n){
n = _n;
logn = 32 - __builtin_clz(n);
t.assign(logn, vector<int> (n));
}
int merge(int a, int b){
return min(a, b);
}
void build(vector<int> &a){
init(len(a));
//cout << n << endl;
for(int i = 0; i < n; i ++) t[0][i] = a[i];
for(int j = 1; j < logn; j ++){
for(int i = 0; i + (1 << j) - 1 < n; i ++){
t[j][i] = merge(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
}
}
}
int get(int l, int r){
if(l > r) return inf;
int k = 31 - __builtin_clz(r - l + 1);
return merge(t[k][l], t[k][r - (1 << k) + 1]);
}
};
struct Sparsemax{
int n, logn;
vector<vector<int>> t;
Sparsemax (){}
void init(int _n){
n = _n;
logn = 32 - __builtin_clz(n);
t.assign(logn, vector<int> (n));
}
int merge(int a, int b){
return max(a, b);
}
void build(vector<int> &a){
init(len(a));
//cout<< n << endl;
for(int i = 0; i < n; i ++) t[0][i] = a[i];
for(int j = 1; j < logn; j ++){
for(int i = 0; i + (1 << j) - 1 < n; i ++){
t[j][i] = merge(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
}
}
}
int get(int l, int r){
if(l > r) return -inf;
int k = 31 - __builtin_clz(r - l + 1);
return merge(t[k][l], t[k][r - (1 << k) + 1]);
}
};
vector<int> check_validity(int N, std::vector<int> x, std::vector<int> y,
std::vector<int> s, std::vector<int> e,
std::vector<int> l, std::vector<int> r) {
n = N;
q = len(s);
m = len(x);
vector<int> res(q);
g.resize(n);
for(int i = 0; i < m; i ++){
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
int mn = 0;
for(int i = 1; i < n; i++) if(len(g[i]) == 1) mn = i;
dfs(mn);
Sparsemin hum; Sparsemax wolf;
hum.build(line); wolf.build(line);
vector<int> pos(n);
for(int i = 0; i < n; i++) pos[line[i]] = i;
for(int i = 0; i < q; i ++){
s[i] = pos[s[i]];
e[i] = pos[e[i]];
int lb = -1, rb = s[i];
while(rb - lb > 1){
int mid = (lb + rb) / 2;
if(hum.get(mid, s[i]) < l[i]){
lb = mid;
}else rb = mid;
}
int hl = rb;
lb = s[i], rb = n;
while(rb - lb > 1){
int mid = (lb + rb) / 2;
if(hum.get(s[i], mid) < l[i]){
rb = mid;
}else lb = mid;
}
int hr = lb;
lb = -1, rb = e[i];
while(rb - lb > 1){
int mid = (lb + rb) / 2;
if(wolf.get(mid, e[i]) > r[i]){
lb = mid;
}else rb = mid;
}
int wl = rb;
lb = -1, rb = e[i];
while(rb - lb > 1){
int mid = (lb + rb) / 2;
if(wolf.get(e[i], mid) > r[i]){
rb = mid;
}else lb = mid;
}
int wr = lb;
//cout << hl << ' ' << hr << endl;
res[i] = not(wl > hr || hl > wr);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
298 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
298 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
710 ms |
69192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
298 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
