#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> edge[200005];
bool visited[200005], ok;
int n, pos[200005];
int l,r;
vector<int > mn[30],mx[30],a,ans;
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;
void build_tree() {
for(int i = 0; i < 30; i ++) {
if((1 << i) >= n) {level = i; break;}
}
for(int i = 0; i < (1 << level); i ++) {
if(i < n) {
mx[level].pb(a[i]);
mn[level].pb(a[i]);
}
else {
mx[level].pb(0);
mn[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]));
mn[i].pb(min(mn[i + 1][j], mn[i + 1][j - 1]));
}
}
}
void dfs(int k, int x, int type, int L, int R) {
int y = (1 << (level - k)) * x;
int z = (1 << (level - k)) * (x + 1) - 1;
if(L <= y && z <= R) {
if(type == 0) ret = min(ret, mn[k][x]);
else ret = max(ret, mx[k][x]);
return;
}
if(z < L || y > R || k == level) return;
dfs(k + 1, x * 2, type, L, R);
dfs(k + 1, x * 2 + 1, type, L, R);
}
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;}
build_tree();
for(int i = 0; i < S.size(); i ++) {
if(S[i] < L[i] || E[i] > R[i]) {ans.pb(0); continue;}
if(pos[S[i]] <= pos[E[i]]) {
l = pos[S[i]];
r = pos[E[i]];
if(l == r) {ans.pb(1); continue;}
while(l < r) {
int mid = (l + r) / 2;
ret = 1e9;
dfs(0,0,0,pos[S[i]],mid);
if(ret >= L[i]) l = mid;
else r = mid - 1;
}
if(a[l] == E[i]) {ans.pb(1); continue;}
ret = 0;
dfs(0,0,1,l + 1, pos[R[i]]);
if(ret <= R[i]) ans.pb(1);
else ans.pb(0);
}
else {
l = pos[E[i]];
r = pos[S[i]];
while(l < r) {
int mid = (l + r) / 2;
ret = 1e9;
dfs(0,0,0,mid, pos[S[i]]);
if(ret >= L[i]) r = mid;
else r = mid + 1;
}
if(a[l] == S[i]) {ans.pb(1); continue;}
ret = 0;
dfs(0,0,1,pos[E[i]], l - 1);
if(ret <= R[i]) ans.pb(1);
else ans.pb(0);
}
}
return ans;
}
Compilation message
werewolf.cpp: In function 'void build_tree()':
werewolf.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | 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:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0; i < X.size(); i ++) {
| ~~^~~~~~~~~~
werewolf.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = 0; i < S.size(); i ++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4069 ms |
4948 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4069 ms |
4948 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4048 ms |
35852 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4069 ms |
4948 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
