#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
const int LOGN = 20;
vector<int> adj[MAXN], ans;
pair<bool, int> dp[MAXN][2];
int to, l, r, idx;
int min_table[MAXN][LOGN], max_table[MAXN][LOGN];
int a[MAXN], ptr[MAXN], n = 0;
bool solve(int u, bool stage){
pair<bool, int> &p = dp[u][stage];
if(p.second == idx){
return p.first;
}
if(u == to){
if(stage || (u >= l && u <= r)){
return true;
}
return false;
}
if(!stage && u < l){
return false;
}
if(stage && u > r){
return false;
}
p.second = idx;
p.first = false;
if(!stage && u <= r){
if(solve(u, true)){
p.first = true;
return true;
}
}
for(int v: adj[u]){
if(solve(v, stage)){
p.first = true;
return true;
}
}
return false;
}
void make_a(int i, int pr = -1){
a[n++] = i;
for(int v: adj[i]){
if(v != pr){
make_a(v, i);
}
}
}
void init_table(){
for(int i = 0; i < n; i++){
min_table[i][0] = a[i];
max_table[i][0] = a[i];
}
for(int j = 1; j < LOGN; j++){
for(int i = 0; i < n; i++){
max_table[i][j] = max(max_table[i][j - 1], max_table[min(n - 1, i + (1 << (j - 1)))][j - 1]);
min_table[i][j] = min(min_table[i][j - 1], min_table[min(n - 1, i + (1 << (j - 1)))][j - 1]);
}
}
}
int calc_min(int from, int to){
int d = to - from + 1, x = 0;
while((1 << x) <= d){
x++;
}
x--;
return min(min_table[from][x], min_table[to - (1 << x) + 1][x]);
}
int calc_max(int from, int to){
int d = to - from + 1, x = 0;
while((1 << x) <= d){
x++;
}
x--;
return max(max_table[from][x], max_table[to - (1 << x) + 1][x]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
for(int i = 0; i < X.size(); i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
if(true){
//if(N > 3000){
for(int i = 0; i < N; i++){
if(adj[i].size() == 1){
make_a(i);
break;
}
}
//for(int i = 0; i < n; i++){
// cout << a[i] << " ";
//}
//cout << endl;
init_table();
for(int i = 0; i < n; i++){
ptr[a[i]] = i;
}
for(int i = 0; i < (int)E.size(); i++){
int s = ptr[S[i]], e = ptr[E[i]];
l = L[i];
r = R[i];
//cout << s << " s e " << e << endl;
if(s > e){
swap(s, e);
int bl = s, br = e + 1;
while(bl != br){
int mid = (bl + br) / 2;
if(calc_max(s, mid) > r){
br = mid;
}
else{
bl = mid + 1;
}
}
br--;
if(br < s){
ans.push_back(false);
continue;
}
bl = s;
if(calc_max(bl, br) < l){
ans.push_back(false);
continue;
}
int right_end = br;
while(bl != br){
int mid = (bl + br + 1) / 2;
if(calc_max(mid, right_end) < l){
br = mid - 1;
}
else{
bl = mid;
}
}
if(calc_max(s, bl) > r || calc_min(bl, e) < l){
ans.push_back(false);
}
else{
ans.push_back(true);
}
}
else{
int bl = s, br = e + 1;
while(bl != br){
int mid = (bl + br) / 2;
if(calc_min(s, mid) < l){
br = mid;
}
else{
bl = mid + 1;
}
}
br--;
if(br < s){
ans.push_back(false);
continue;
}
bl = s;
if(calc_min(bl, br) > r){
ans.push_back(false);
continue;
}
int right_end = br;
while(bl != br){
int mid = (bl + br + 1) / 2;
if(calc_min(mid, right_end) > r){
br = mid - 1;
}
else{
bl = mid;
}
}
if(calc_min(s, bl) < l || calc_max(bl, e) > r){
ans.push_back(false);
}
else{
ans.push_back(true);
}
}
}
return ans;
}
for(int i = 0; i < S.size(); i++){
to = E[i];
l = L[i];
r = R[i];
idx = i + 1;
ans.push_back(solve(S[i], false));
}
return ans;
}
/*vector<int> xv, yv, sv, ev, lv, rv;
int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
xv.push_back(x);
yv.push_back(y);
}
int q;
cin >> q;
for(int i = 0; i < q; i++){
int sx, ex, lx, rx;
cin >> sx >> ex >> lx >> rx;
sv.push_back(sx);
ev.push_back(ex);
lv.push_back(lx);
rv.push_back(rx);
}
vector<int> res = check_validity(n, xv, yv, sv, ev, lv, rv);
for(int t: res){
cout << t << " ";
}
cout << endl;
return 0;
}*/
/*
2 1
0 1
2
0 1 1 1
1 0 1 2
*/
Compilation message
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:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < X.size(); i++){
~~^~~~~~~~~~
werewolf.cpp:235:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < S.size(); i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1335 ms |
524288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1335 ms |
524288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
730 ms |
70616 KB |
Output is correct |
| 2 |
Correct |
1100 ms |
73068 KB |
Output is correct |
| 3 |
Correct |
1063 ms |
73072 KB |
Output is correct |
| 4 |
Correct |
993 ms |
73160 KB |
Output is correct |
| 5 |
Correct |
972 ms |
73100 KB |
Output is correct |
| 6 |
Correct |
858 ms |
73052 KB |
Output is correct |
| 7 |
Correct |
862 ms |
73388 KB |
Output is correct |
| 8 |
Correct |
942 ms |
73160 KB |
Output is correct |
| 9 |
Correct |
531 ms |
72972 KB |
Output is correct |
| 10 |
Correct |
516 ms |
73036 KB |
Output is correct |
| 11 |
Correct |
529 ms |
73140 KB |
Output is correct |
| 12 |
Correct |
604 ms |
73184 KB |
Output is correct |
| 13 |
Correct |
990 ms |
73332 KB |
Output is correct |
| 14 |
Correct |
960 ms |
73072 KB |
Output is correct |
| 15 |
Correct |
1000 ms |
73184 KB |
Output is correct |
| 16 |
Correct |
1008 ms |
73216 KB |
Output is correct |
| 17 |
Correct |
818 ms |
73000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1335 ms |
524288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
