# include <bits/stdc++.h>
# include "werewolf.h"
using namespace std;
const int maxn = 2e5 + 2;
int p[2][maxn], timer, tin[3][maxn], tout[3][maxn], up[3][19][maxn], pos[maxn], fen[maxn];
vector <int> g[3][maxn];
int f_s(int tp, int v){
return p[tp][v] == v?v:p[tp][v] = f_s(tp, p[tp][v]);
}
void dfs(int tp, int v, int pr){
tin[tp][v] = ++ timer;
up[tp][0][v] = pr;
for(int i = 1; i <= 18; i ++)
up[tp][i][v] = up[tp][i - 1][ up[tp][i - 1][v] ];
for(int to : g[tp][v]){
if(to == pr)
continue;
dfs(tp, to, v);
}
tout[tp][v] = timer;
}
void upd(int pos){
for(; pos < maxn; pos |= pos + 1)
fen[pos] ++;
}
int get(int r){
int ret = 0;
for(; r > 0; r = (r & (r + 1)) - 1)
ret += fen[r];
return ret;
}
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(), M = X.size();
vector<int> A(Q);
for(int i = 0; i < M; i ++){
g[0][X[i]].push_back(Y[i]);
g[0][Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; i ++)
p[0][i] = p[1][i] = i;
for(int i = N - 1; i >= 0; i --){
for(int to : g[0][i]){
if(to < i || f_s(0, i) == f_s(0, to))
continue;
int a = f_s(0, i), b = f_s(0, to);
g[1][a].push_back(b);
p[0][b] = a;
}
}
for(int i = 0; i < N; i ++){
for(int to : g[0][i]){
if(to > i || f_s(1, i) == f_s(1, to))
continue;
int a = f_s(1, i), b = f_s(1, to);
g[2][a].push_back(b);
p[1][b] = a;
}
}
dfs(1, f_s(0, 0), f_s(0, 0));
timer = 0;
dfs(2, f_s(1, 0), f_s(1, 0));
vector < pair <int, pair <int, int> > > qe;
for(int i = 0; i < Q; i ++){
int s = S[i], e = E[i], l = L[i], r = R[i];
for(int j = 18; j >= 0; j --){
if(up[1][j][s] >= l)
s = up[1][j][s];
}
for(int j = 18; j >= 0; j --){
if(up[2][j][e] <= r)
e = up[2][j][e];
}
qe.push_back({tin[1][s] - 1, {-(i + 1), e}});
qe.push_back({tout[1][s], {i + 1, e}});
}
sort(qe.begin(), qe.end());
for(int i = 0; i < N; i ++)
pos[ tin[1][i] - 1 ] = tin[2][i];
int pt = 0;
for(int i = 0; i < qe.size(); i ++){
int p = qe[i].first, id = qe[i].second.first, v = qe[i].second.second;
while(pt < p)
upd(pos[pt ++]);
if(id < 0)
A[abs(id) - 1] -= get(tout[2][v]) - get(tin[2][v]);
else
A[abs(id) - 1] += get(tout[2][v]) - get(tin[2][v]);
}
for(int i = 0; i < Q.size(); i ++)
A[i] = (A[i] > 0);
return A;
}
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:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < qe.size(); i ++){
~~^~~~~~~~~~~
werewolf.cpp:109:28: error: request for member 'size' in 'Q', which is of non-class type 'int'
for(int i = 0; i < Q.size(); i ++)
^~~~
