#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
const int N = 2e5 + 5;
struct ST{
int mx[N << 2];
void set(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx) { mx[x] = v; return; }
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
int get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return mx[x];
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
}tree;
vector<int> edges[2][N];
int c[N], lift[2][N][20];
int tin[2][N], tout[2][N], t_;
int par[N];
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(), t;
function<int(int)> f = [&](int x){ return (par[x] == x ? x : par[x] = f(par[x])); };
auto merge = [&](int a, int b){
a = f(a), b = f(b);
if(a == b){
return;
}
if(b > a && !t) swap(a, b);
if(a > b && t) swap(a, b);
edges[t][a].push_back(b);
par[b] = a;
};
vector<ar<int, 2>> e;
for(int i=0;i<m;i++){
e.push_back({max(X[i], Y[i]), i});
} sort(e.begin(), e.end());
iota(par, par + n, 0);
t = 0;
for(auto [c, i] : e){
merge(X[i], Y[i]);
} int r1 = f(0);
e.clear();
for(int i=0;i<m;i++){
e.push_back({min(X[i], Y[i]), i});
} sort(e.rbegin(), e.rend());
iota(par, par + n, 0);
t = 1;
for(auto [c, i] : e){
merge(X[i], Y[i]);
} int r2 = f(0);
//~ for(int i=0;i<m;i++){
//~ cout<<X[i] + n<<" "<<Y[i] + n<<"\n";
//~ }
//~ for(int i=0;i<n;i++){
//~ for(auto x : edges[0][i]) cout<<i<<" "<<x<<"\n";
//~ } cout<<"\n";
//~ for(int i=0;i<n;i++){
//~ for(auto x : edges[1][i]) cout<<i<<" "<<x<<"\n";
//~ } cout<<"\n";
//~ cout<<r1<<" "<<r2<<"\n";
vector<int> V;
function<void(int)> dfs = [&](int u){
tin[t][u] = ++t_;
if(t) V.push_back(u);
for(int j=1;j<20;j++){
lift[t][u][j] = lift[t][lift[t][u][j-1]][j-1];
}
for(auto x : edges[t][u]){
lift[t][x][0] = u;
dfs(x);
}
tout[t][u] = t_;
};
t = 0; t_ = 0;
lift[t][r1][0] = r1;
dfs(r1);
t = 1; t_ = 0;
lift[t][r2][0] = r2;
dfs(r2);
assert((int)V.size() == n);
int q = S.size();
vector<int> p(q); iota(p.begin(), p.end(), 0);
for(int i=0;i<q;i++){
int v = S[i];
for(int j=19;~j;j--){
if(lift[1][v][j] >= L[i]) v = lift[1][v][j];
}
S[i] = v;
v = E[i];
for(int j=19;~j;j--){
if(lift[0][v][j] <= R[i]) v = lift[0][v][j];
}
E[i] = v;
}
//~ assert(false);
sort(p.begin(), p.end(), [&](int i, int j){
return tout[1][S[p[i]]] < tout[1][S[p[j]]];
});
assert(false);
vector<int> res(q);
int j = 0;
for(auto i : p){ int x = S[i];
while(j < n && j + 1 <= tout[1][x]){
tree.set(tin[0][V[j]], tin[1][V[j]]);
j++;
}
res[i] = (tree.get(tin[0][E[i]], tout[0][E[i]]) >= tin[1][x]);
}
return res;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
6 5 2
0 3
3 2
2 1
1 5
5 4
2 5 2 5
3 1 3 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
19548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
19548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1512 ms |
133800 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
19548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
