#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> stx, stn;
void updatex(int pos, int val, int node=1, int tl=0, int tr=n-1){
if (tl == tr){
stx[node] = val;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) updatex(pos, val, node*2, tl, tm);
else updatex(pos, val, node*2+1, tm+1, tr);
stx[node] = max(stx[node*2], stx[node*2+1]);
}
int queryx(int l, int r, int node=1, int tl=0, int tr=n-1){
if (l <= tl && tr <= r) return stx[node];
int tm = (tl+tr)/2;
int res = -1;
if (l <= tm) res = max(res, queryx(l, r, node*2, tl, tm));
if (tm+1 <= r) res = max(res, queryx(l, r, node*2+1, tm+1, tr));
return res;
}
void updaten(int pos, int val, int node=1, int tl=0, int tr=n-1){
if (tl == tr){
stn[node] = val;
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) updaten(pos, val, node*2, tl, tm);
else updaten(pos, val, node*2+1, tm+1, tr);
stn[node] = min(stn[node*2], stn[node*2+1]);
}
int queryn(int l, int r, int node=1, int tl=0, int tr=n-1){
if (l <= tl && tr <= r) return stn[node];
int tm = (tl+tr)/2;
int res = 200000;
if (l <= tm) res = min(res, queryn(l, r, node*2, tl, tm));
if (tm+1 <= r) res = min(res, queryn(l, r, node*2+1, tm+1, tr));
return res;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
n = N;
vector<vector<int>> g(N);
for (int i=0; i<X.size(); i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<bool> seen(N, false);
int cur;
for (int i=0; i<N; i++){
if (g[i].size() == 1){
cur = i;
break;
}
}
stx = {};
stx.resize(4*N, -1);
stn = {};
stn.resize(4*N, 200000);
int pos = 0;
vector<int> v(N);
while (true){
seen[cur] = true;
updatex(pos, cur);
updaten(pos, cur);
v[cur] = pos;
pos++;
for (int next : g[cur]){
if (!seen[next]) cur = next;
}
if (seen[cur]) break;
}
vector<int> A(S.size(), 0);
for (int i=0; i<S.size(); i++){
int s = v[S[i]], e = v[E[i]];
if (s < e){
int l = s, r = e+1;
while (l != r-1){
int m = (l+r)/2;
if (queryn(l, m) > L[i]) l = m;
else r = m;
}
int rh = l;
l = s; r = e+1;
while (l != r-1){
int m = (l+r)/2;
if (queryx(m-1, r-1) < R[i]) r = m;
else l = m;
}
int lw = l;
if (lw < rh) A[i] = 1;
}
else {
int r = s, l = e+1;
while (l != r-1){
int m = (l+r)/2;
if (queryx(l, m) < R[i]) l = m;
else r = m;
}
int rw = l;
l = s; r = e+1;
while (l != r-1){
int m = (l+r)/2;
if (queryn(m-1, r-1) > L[i]) r = m;
else l = m;
}
int lh = l;
if (lh < rw) A[i] = 1;
}
}
return A;
}
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:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i=0; i<X.size(); i++){
| ~^~~~~~~~~
werewolf.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i=0; i<S.size(); i++){
| ~^~~~~~~~~
werewolf.cpp:70:13: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
70 | seen[cur] = true;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4070 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4070 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4072 ms |
28500 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4070 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
