#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
vector<int> edge[200005];
bool visited[200005], ok;
int n, pos[200005];
int l,r;
vector<int > mn[30],mx[30],a,ans;
pair<int,int> p[200005];
int parent[200005], dad[200005];
void dfs(int node) {
visited[node] = 1;
pos[node] = a.size();
a.pb(node);
for(auto x: edge[node]) if(visited[x] == 0) dfs(x);
}
int level, ret, zereg[30];
void build_tree() {
zereg[0] = 1;
for(int i = 0; i < 30; i ++) {
if(zereg[i] >= n) {level = i; break;}
zereg[i + 1] = zereg[i] * 2;
}
for(int i = 0; i < zereg[level]; i ++) {
if(i < n) {
mx[level].pb(a[i]);
}
else {
mx[level].pb(0);
}
}
for(int i = level - 1; i >= 0; i --) {
for(int j = 1; j < mx[i + 1].size(); j += 2) {
mx[i].pb(max(mx[i + 1][j], mx[i + 1][j - 1]));
}
}
}
void dfs(int k, int x, int L, int R) {
int y = zereg[level - k] * x;
int z = zereg[level - k] * (x + 1) - 1;
if(L <= y && z <= R) {
ret = max(ret, mx[k][x]);
return;
}
if(z < L || y > R || k == level) return;
dfs(k + 1, x * 2, L, R);
dfs(k + 1, x * 2 + 1, L, R);
}
int find(int node) {
if(parent[node] == node) return node;
return parent[node] = find(parent[node]);
}
int d_find(int node) {
if(dad[node] == node) return node;
return dad[node] = d_find(dad[node]);
}
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) {
n = N;
for(int i = 0; i < X.size(); i ++) {
edge[X[i]].pb(Y[i]);
edge[Y[i]].pb(X[i]);
}
for(int i = 0; i < N; i ++) if(edge[i].size() == 1) {dfs(i); break;}
for(int i = 0; i < N; i ++) {parent[i] = i; dad[i] = i;}
for(int i = 0; i < S.size(); i ++) {
p[i].ff = -L[i];
p[i].ss = i;
}
sort(p, p + S.size());
build_tree();
//
for(int j = 0; j < S.size(); j ++) {
int i = p[j].ss;
if(S[i] < L[i] || E[i] > R[i]) {ans.pb(0); continue;}
if(pos[S[i]] < pos[E[i]]) {
int A = find(S[i]);
if(pos[A] >= pos[E[i]]) {ans.pb(1); continue;}
while(pos[A] < pos[E[i]]) {
if(a[pos[A] + 1] >= L[i]) {parent[A] = find(a[pos[A] + 1]); A = parent[A];}
else break;
}
if(pos[A] >= pos[E[i]]) {ans.pb(1); continue;}
ret = -1;
dfs(0,0,pos[A],pos[E[i]]);
if(ret <= R[i]) ans.pb(1);
else ans.pb(0);
}
else {
int A = d_find(S[i]);
if(pos[A] <= pos[E[i]]) {ans.pb(1); continue;}
while(pos[A] > pos[E[i]]) {
if(a[pos[A] - 1] >= L[i]) {dad[A] = d_find(dad[a[pos[A] - 1]]); A = dad[A];}
else break;
}
if(pos[A] <= pos[E[i]]) {ans.pb(1); continue;}
ret = -1;
dfs(0,0,pos[E[i]],pos[A]);
if(ret <= R[i]) ans.pb(1);
else ans.pb(0);
}
}
//
return ans;
}
Compilation message
werewolf.cpp: In function 'void build_tree()':
werewolf.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int j = 1; j < mx[i + 1].size(); j += 2) {
| ~~^~~~~~~~~~~~~~~~~~
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:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0; i < X.size(); i ++) {
| ~~^~~~~~~~~~
werewolf.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0; i < S.size(); i ++) {
| ~~^~~~~~~~~~
werewolf.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int j = 0; j < S.size(); j ++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
447 ms |
38668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
