#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int find(int a, vector<int>& rep){
if(rep[a] != a)rep[a] = find(rep[a], rep);
return rep[a];
}
void uni(int a, int b, vector<int>& rep, vector<set<int>>& pos){
a = find(a, rep); b = find(b, rep);
if(a != b){
if(pos[a].size() < pos[b].size())swap(a, b);
rep[b] = a;
pos[a].insert(pos[b].begin(), pos[b].end());
pos[b].clear();
}
}
void computeRange(int v, vector<pair<int, int>>& children, vector<pair<int, int>>& range, int& cnt){
if(children[v] == make_pair(-1, -1)){
range[v] = {cnt, cnt}; cnt++;
}else{
computeRange(children[v].first, children, range, cnt);
computeRange(children[v].second, children, range, cnt);
range[v] = {range[children[v].first].first, range[children[v].second].second};
}
}
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();
int Q = S.size();
vector<vector<int>> smaller(N);
vector<vector<int>> bigger(N);
for(int j = 0; j < M; j++){
int x, y; x = X[j]; y = Y[j];
if(x > y)swap(x, y);
bigger[x].push_back(y);
smaller[y].push_back(x);
}
vector<array<int, 20>> jump(N);
vector<array<int, 20>> jumpR(N);
vector<pair<int, int>> children(N, {-1, -1});
vector<int> repR(N); for(int i = 0; i < N; i++)repR[i] = i;
int id = N;
//cout<<"WOW\n";
for(int r = 1; r < N; r++){
for(auto l : smaller[r]){
int x = find(l, repR); int y = find(r, repR);
if(x != y){
repR.push_back(id);
jump.push_back(array<int, 20>());
jumpR.push_back(array<int, 20>());
jump[x][0] = id; jump[y][0] = id; repR[x] = id; repR[y] = id;
id++;
jumpR[x][0] = r; jumpR[y][0] = r;
jump[id][0] = id;
jumpR[id][0] = r;
children.push_back({x, y});
}
}
}
//cout<<"XD\n";
vector<pair<int, int>> range(id);
int cnt = 0;
computeRange(id-1, children, range, cnt);
/*for(int i = 0; i < id; i++){
cout<<children[i].first<<" "<<children[i].second<<" "<<jump[i][0]<<" "<<jumpR[i][0]<<" "<<range[i].first<<" "<<range[i].second<<"\n";
}*/
vector<int> A(Q);
for(int k= 1; k < 20; k++){
for(int i = 0; i < id; i++){
jump[i][k] = jump[jump[i][k-1]][k-1];
jumpR[i][k] = jumpR[jump[i][k-1]][k-1];
}
}
vector<array<int, 3>> queries;
vector<int> rep(N);
for(int i= 0; i < N; i++)rep[i] = i;
vector<set<int>> pos(N);
for(int i = 0; i < N; i++)pos[i].insert(range[i].first);
for(int i =0; i < Q; i++){
queries.push_back({L[i], R[i], i});
}
sort(queries.begin(), queries.end(), greater<array<int, 3>>());
int currentL = N-1;
for(auto query : queries){
int L = query[0]; int R = query[1]; int ansId = query[2];
while(L < currentL){
currentL--;
for(auto x : bigger[currentL]){
uni(x, currentL, rep, pos);
}
}
int v = E[ansId];
for(int k = 19; k >= 0; k--){
if(jumpR[v][k] <= R){
v = jump[v][k];
}
}
int x = S[ansId];
x = find(x, rep);
auto it = pos[x].lower_bound(range[v].first);
if(it != pos[x].end() && (*it) <= range[v].second){
A[ansId] = 1;
}else{
A[ansId] = 0;
}
}
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
861 ms |
123784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
