#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int nax = 2e5 + 10;
vector<int>a[nax], b[nax];
bool vis[nax];
// vector<int>stk1, stk2;
// void dfs1(int v) {
// vis[v] = 1;
// stk1.push_back(v);
// for(int u : a[v]) if(!vis[u]) {
// dfs1(u);
// }
// }
// void dfs2(int v) {
// vis[v] = 1;
// stk2.push_back(v);
// for(int u : b[v]) if(!vis[u]) {
// dfs2(u);
// }
// }
vector<int>stk;
void dfs(int v) {
vis[v] = 1;
stk.push_back(v);
for(int u : a[v]) if(!vis[u]) {
dfs(u);
}
}
vector<int>ord;
struct node {
int mn, mx;
node() {}
node(int i) {
mn = mx = ord[i];
}
node(int x, int y) {
mn = x, mx = y;
}
} tree[nax * 4];
node merge(node x, node y) {
node ret;
ret.mn = min(x.mn, y.mn);
ret.mx = max(x.mx, y.mx);
return ret;
}
void build(int l, int r, int v) {
if(l==r) {
tree[v] = node(l-1);
return;
}
int mid = (l+r)/2;
build(l, mid, v*2), build(mid+1, r, v*2+1);
tree[v] = merge(tree[v*2], tree[v*2+1]);
}
node query(int l, int r, int L, int R, int v) {
if(l>=L && r<=R) return tree[v];
if(l>R || r<L) return node(1e9, -1e9);
int mid = (l+r)/2;
return merge(query(l, mid, L, R, v*2), query(mid+1, r, L, R, v*2+1));
}
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 q = S.size();
int m = X.size();
vector<int>ans(q);
for(int i=0; i<m; ++i) {
a[X[i]].push_back(Y[i]);
a[Y[i]].push_back(X[i]);
}
memset(vis, 0, sizeof vis);
for(int i=0; i<N; ++i) if(a[i].size()==1) {
dfs(i);
ord = stk;
break;
}
vector<int>invord(N);
for(int i=0; i<N; ++i) {
invord[ord[i]] = i;
}
build(1, N, 1);
for(int i=0; i<q; ++i) {
vector<pair<int,int>>bag;
bool f = true;
for(int x : {S[i], E[i]}) {
int l = 0, r = N - invord[x] - 1;
while(l<r) {
int mid = (l+r+1)/2;
node cr = query(1, N, invord[x]+1, invord[x]+mid+1, 1);
if(f) {
if(cr.mn>=L[i]) {
l = mid;
} else {
r = mid-1;
}
} else {
if(cr.mx<=R[i]) {
l = mid;
} else {
r = mid-1;
}
}
}
int rit = invord[x] + l;
l = 0, r = invord[x];
while(l<r) {
int mid = (l+r+1)/2;
node cr = query(1, N, invord[x]-mid+1, invord[x]+1, 1);
if(f) {
if(cr.mn>=L[i]) {
l = mid;
} else {
r = mid-1;
}
} else {
if(cr.mx<=R[i]) {
l = mid;
} else {
r = mid-1;
}
}
}
int lef = invord[x] - l;
bag.emplace_back(lef, rit);
f = false;
}
if(bag[0].first>=bag[1].first && bag[0].first<=bag[1].second) {
ans[i] = 1;
} else if(bag[1].first>=bag[0].first && bag[1].first<=bag[0].second) {
ans[i] = 1;
}
}
return ans;
// for(int i=0; i<q; ++i) {
// for(int j=0; j<N; ++j) {
// a[j].clear(), b[j].clear();
// }
// for(int j=0; j<m; ++j) {
// int u = X[j], v = Y[j];
// if(min(u, v) >= L[i]) {
// a[u].push_back(v);
// a[v].push_back(u);
// }
// if(max(u, v) <= R[i]) {
// b[u].push_back(v);
// b[v].push_back(u);
// }
// }
// stk1.clear(), stk2.clear();
// memset(vis, 0, sizeof vis);
// dfs1(S[i]);
// memset(vis, 0, sizeof vis);
// dfs2(E[i]);
// int cnt[N] = {0};
// for(int x : stk1) {
// if(x>=L[i] && x<=R[i]) {
// cnt[x]++;
// }
// }
// for(int x : stk2) {
// if(x>=L[i] && x<=R[i]) {
// cnt[x]++;
// if(cnt[x]>1) {
// ans[i] = 1;
// }
// }
// }
// }
// return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3997 ms |
50756 KB |
Output is correct |
| 2 |
Execution timed out |
4021 ms |
50744 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
