#include "werewolf.h"
#include <bits/stdc++.h>
const int MAX_N = 200000;
const int MAX_Q = 200000;
std::vector<int> graph[MAX_N], graph1[MAX_N], graph2[MAX_N];
std::vector<int> queryId[MAX_N];
int par1[20][MAX_N+1], par2[20][MAX_N+1];
int entryT[MAX_N], exitT[MAX_N];
int top, eulertour[1+MAX_N], poz[1+MAX_N];
int subarb[1+MAX_N];
int aib[1+MAX_N];
int sef1[MAX_N], sef2[MAX_N];
bool bl1[MAX_N], bl2[MAX_N];
static inline int lsb(int x) {
return x & (-x);
}
void updateAib(int poz, int val) {
while(poz <= MAX_N) {
aib[poz] += val;
poz += lsb(poz);
}
}
int queryAib(int poz) {
int rez = 0;
while(poz > 0) {
rez += aib[poz];
poz -= lsb(poz);
}
return rez;
}
struct Query {
int a, b, rez;
} query[MAX_Q];
void calcBinaryLifting(int n) {
for(int l = 1; l < 20; ++l)
for(int i = 0; i < n; ++i) {
par1[l][i] = par1[l - 1][par1[l - 1][i]];
par2[l][i] = par2[l - 1][par2[l - 1][i]];
}
}
int searchSmaller(int src, int val) {
for(int l = 2; l >= 0; --l) {
int jump = par1[l][src];
if(jump != MAX_N && jump <= val)
src = jump;
}
return src;
}
int searchGreater(int src, int val) {
for(int l = 19; l >= 0; --l) {
int jump = par2[l][src];
if(jump != MAX_N && jump >= val)
src = jump;
}
return src;
}
void dfs(int nod) {
entryT[nod] = top + 1;
for(auto it: graph1[nod])
dfs(it);
poz[nod] = ++top;
eulertour[top] = nod;
exitT[nod] = top;
}
void dfs2(int nod) {
subarb[nod] = 1;
for(auto it: graph2[nod]) {
dfs2(it);
subarb[nod] += subarb[it];
}
}
void dfs3(int nod, int val = 0) {
int heavySon = -1, heavySize = 0;
for(auto it: graph2[nod])
if(subarb[it] > heavySize) {
heavySize = subarb[it];
heavySon = it;
}
if(val == 0) {
for(auto it: graph2[nod])
if(it != heavySon) {
dfs3(it, val);
dfs3(it, -1);
}
if(heavySon != -1)
dfs3(heavySon, 0);
for(auto it: graph2[nod])
if(it != heavySon)
dfs3(it, 1);
updateAib(poz[nod], 1);
for(auto it: queryId[nod]) {
if(queryAib(exitT[query[it].a]) - queryAib(entryT[query[it].a] - 1) > 0)
query[it].rez = 1;
}
} else {
for(auto it: graph2[nod])
dfs3(it, val);
updateAib(poz[nod], val);
}
}
int myfind(int x, int *sef) {
if(x == sef[x])
return x;
else {
sef[x] = myfind(sef[x], sef);
return sef[x];
}
}
void myunion(int a, int b, int *sef, bool doMin = true) {
int sa = myfind(a, sef), sb = myfind(b, sef);
if((doMin && sa < sb) || (!doMin && sa > sb))
sef[sb] = sa;
else
sef[sa] = sb;
}
std::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) {
int Q = S.size(), M = X.size();
std::vector<int> A(Q);
for(int i = 0; i < M; ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
for(int l = 0; l < 20; ++l)
par1[l][MAX_N] = par2[l][MAX_N] = MAX_N;
for(int i = 0; i < N; ++i)
sef1[i] = sef2[i] = i;
for(int i = 0; i < N; ++i) {
par1[0][i] = par2[0][i] = MAX_N;
for(auto it: graph[i])
if(it < i && myfind(i, sef1) != myfind(it, sef1)) {
par1[0][myfind(it, sef1)] = i;
graph1[i].push_back(myfind(it, sef1));
myunion(i, it, sef1, false);
}
}
for(int i = N - 1; i >= 0; --i)
for(auto it: graph[i])
if(it > i && myfind(i, sef2) != myfind(it, sef2)) {
par2[0][myfind(it, sef2)] = i;
graph2[i].push_back(myfind(it, sef2));
myunion(i, it, sef2);
}
calcBinaryLifting(N);
dfs(N - 1);
dfs2(0);
for(int i = 0; i < Q; ++i) {
query[i].a = searchSmaller(E[i], R[i]);
query[i].b = searchGreater(S[i], L[i]);
queryId[query[i].b].push_back(i);
}
dfs3(0);
for(int i = 0; i < Q; ++i)
A[i] = query[i].rez;
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
19448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
19448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1087 ms |
87060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
19448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
