#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
vector<int>graf[maxn];
int father1[maxn], father2[maxn], ojciec1[maxn], ojciec2[maxn];
int find1(int x){
if(father1[x] == x)return x;
return father1[x] = find1(father1[x]);
}
int find2(int x){
if(father2[x] == x)return x;
return father2[x] = find2(father2[x]);
}
int pre[maxn], post[maxn], preit;
vector<int>graf2[maxn], graf1[maxn];
void dfs(int x){
pre[x] = preit++;
for(auto j: graf1[x])
dfs(j);
post[x] = preit;
}
vector<int> A;
vector<pair<pair<int,int>, int>>przedzialy[maxn];
int pocz, kon, it;
void dfs2(int x){
if(pocz<=pre[x] && pre[x]<=kon)
A[it] = 1;
for(auto j: graf2[x])
dfs2(j);
}
int jump1[maxn][19], jump2[maxn][19];
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 i;
for(i=0;i<(int)X.size();i++){
graf[Y[i]].push_back(X[i]);
graf[X[i]].push_back(Y[i]);
}
for(i=0;i<n;i++)
ojciec1[i] = n, ojciec2[i] = -1, father1[i] = father2[i] = i;
for(i=0;i<n;i++){
for(auto j: graf[i])
if(j<i){
if(find1(j) != i)ojciec1[find1(j)] = i;
father1[find1(j)] = i;
}
}
for(i=0;i<n;i++){
graf1[ojciec1[i]].push_back(i);
graf2[ojciec2[i]].push_back(i);
}
for(i=n-1;i>=0;i--)
for(auto j: graf[i])
if(j>i){
if(find2(j) != i)ojciec2[find2(j)] = i;
father2[find2(j)] = i;
}
// for(i=0;i<n;i++)printf("%d ", ojciec1[i]);printf("\n");
// for(i=0;i<n;i++)printf("%d ", ojciec2[i]);printf("\n");
// return {};
for(i=0;i<n;i++){
jump1[i][0] = ojciec1[i];
if(jump1[i][0] == n)jump1[i][0] = i;
}
for(i=0;i<n;i++){
jump2[i][0] = ojciec2[i];
if(jump2[i][0] == -1)jump2[i][0] = i;
}
for(int j=1;j<18;j++)
for(int i=0;i<n;i++){
jump1[i][j] = jump1[jump1[i][j-1]][j-1];
jump2[i][j] = jump2[jump2[i][j-1]][j-1];
}
// for(i=0;i<n;i++)printf("%d ", jump1[i][1]);printf("\n");
// for(i=0;i<n;i++)printf("%d ", jump2[i][1]);printf("\n");
dfs(n);
int q = S.size();
A.resize(q, 0);
for (int i = 0; i < q; ++i) {
if(E[i]>R[i] || S[i]<L[i])continue;
int pom1 = E[i], pom2 = S[i];
for(int j = 17;j>=0;j--){
// printf("%d %d\n", pom1, pom2);
if(jump1[pom1][j]<=R[i])
pom1 = jump1[pom1][j];
if(jump2[pom2][j]>=L[i])
pom2 = jump2[pom2][j];
}
pocz = pre[pom1], kon = post[pom1], it = i;
dfs2(pom2);
// printf("%d: %d %d %d %d\n", i, pom1, pom2, pocz, kon);
// przedzialy[pom2].push_back({{pre[pom1], post[pom1]},i});
}
preit = 0;
// dfs2(n);
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
20316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
20316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
83536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
20316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
