#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 3e2;
vector<int> g[MAXN];
vector<int> vec, ord;
void dfs(int v, int p){
ord[v] = vec.size();
vec.push_back(v);
for (int u : g[v]){
if (u != p) dfs(u, v);
}
}
int Tmin[MAXN][20], Tmax[MAXN][20], Log[MAXN];
int get_min(int l, int r){
if (l > r) return 1e9;
int j = Log[r - l + 1];
return min(Tmin[l][j], Tmin[r - (1 << j) + 1][j]);
}
int get_max(int l, int r){
if (l > r) return -1e9;
int j = Log[r - l + 1];
return max(Tmax[l][j], Tmax[r - (1 << j) + 1][j]);
}
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(), Q = S.size();
vector<int> A(Q, 0);
if (M != N - 1) return A;
for (int i = 0; i < M; i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
ord.resize(N);
for (int i = 0; i < N; i++){
if (g[i].size() == 1){
dfs(i, i);
break;
}
}
Log[1] = 0;
for (int i = 0; i < MAXN; i++){
if (i < N) Tmin[i][0] = Tmax[i][0] = vec[i];
if (i > 1) Log[i] = Log[i / 2] + 1;
}
for (int j = 1; j < 20; j++){
for (int i = 0; i < N; i++){
if (i + (1 << j) - 1 < N){
Tmin[i][j] = min(Tmin[i][j - 1], Tmin[i + (1 << (j - 1))][j - 1]);
Tmax[i][j] = max(Tmax[i][j - 1], Tmax[i + (1 << (j - 1))][j - 1]);
}
}
}
for (int i = 0; i < Q; i++){
S[i] = ord[S[i]], E[i] = ord[E[i]];
if (S[i] < E[i]){
int l = S[i], r = N - 1;
while (l <= r){
int mid = (l + r) >> 1;
if (get_min(S[i], mid) >= L[i]) l = mid + 1; else
r = mid - 1;
}
int x = l - 1;
l = 0, r = E[i];
while (l <= r){
int mid = (l + r) >> 1;
if (get_max(mid, E[i]) <= R[i]) r = mid - 1; else
l = mid + 1;
}
int y = r + 1;
A[i] = x >= y;
} else {
int l = 0, r = S[i];
while (l <= r){
int mid = (l + r) >> 1;
if (get_min(mid, S[i]) >= L[i]) r = mid - 1; else
l = mid + 1;
}
int x = r + 1;
l = E[i], r = N - 1;
while (l <= r){
int mid = (l + r) >> 1;
if (get_max(E[i], mid) <= R[i]) l = mid + 1; else
r = mid - 1;
}
int y = l - 1;
A[i] = x <= y;
}
}
return A;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
503 ms |
70208 KB |
Output is correct |
2 |
Correct |
526 ms |
78644 KB |
Output is correct |
3 |
Correct |
549 ms |
78620 KB |
Output is correct |
4 |
Correct |
536 ms |
78508 KB |
Output is correct |
5 |
Correct |
523 ms |
78512 KB |
Output is correct |
6 |
Correct |
491 ms |
78668 KB |
Output is correct |
7 |
Correct |
566 ms |
78560 KB |
Output is correct |
8 |
Correct |
460 ms |
78672 KB |
Output is correct |
9 |
Correct |
362 ms |
78504 KB |
Output is correct |
10 |
Correct |
329 ms |
78496 KB |
Output is correct |
11 |
Correct |
374 ms |
78496 KB |
Output is correct |
12 |
Correct |
351 ms |
78512 KB |
Output is correct |
13 |
Correct |
579 ms |
78628 KB |
Output is correct |
14 |
Correct |
529 ms |
78500 KB |
Output is correct |
15 |
Correct |
535 ms |
78536 KB |
Output is correct |
16 |
Correct |
546 ms |
78684 KB |
Output is correct |
17 |
Correct |
563 ms |
78696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
9676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |