#include <bits/stdc++.h>
#include "werewolf.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
const ll NMAX = 200001;
const int INF = 2e9;
const ll MOD = 998244353;
const ll p = 31;
const ll BLOCK = 101;
const ll nr_of_bits = 18;
vector <int> init[NMAX];
class Arbore {
int parent[NMAX];
vector <int> v[NMAX];
int stamp = 0;
public:
pii timp[NMAX];
int dp[NMAX][nr_of_bits];
vector <int> parcurgere;
int n;
void Init(int _n) {
n = _n;
parcurgere.push_back(0);
for(int i = 0; i <= n + 1; i++) {
parent[i] = 0;
}
}
int root(int x) {
if(parent[x] == 0)
return x;
return (parent[x] = root(parent[x]));
}
void merge(int a, int b) {
a = root(a);
if(a == b)
return;
parent[a] = b;
v[a].push_back(b);
v[b].push_back(a);
}
void DFS(int node, int p) {
timp[node].first = ++stamp;
dp[node][0] = p;
parcurgere.push_back(node);
for(auto x : v[node]) {
if(x == p)
continue;
DFS(x, node);
}
timp[node].second = stamp;
}
void Precalc() {
for(int j = 1; j < nr_of_bits; j++) {
for(int i = 1; i <= n; i++) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
}
} C, D;
class AIB{
int aib[NMAX], n;
public:
void Init(int _n){
n = _n + 1;
}
void update(int x){
for(int i = x; i < n; i += i&(-i)){
aib[i]++;
}
}
int query(int x){
int s = 0;
for(int i = x; i > 0; i -= i&(-i)){
s += aib[i];
}
return s;
}
}aib;
vector <pii> queries[NMAX];
vector <int> Compute(int Q) {
vector <int> rez(Q + 1, 0);
map <int, int> mp;
for(int i = 1; i < D.parcurgere.size(); i++){
mp[D.parcurgere[i]] = i;
//debug_with_space(D.parcurgere[i]);
}
//debug(Q);
aib.Init(D.n);
int i;
for(int i = 1; i <= C.n; i++){
aib.update(mp[C.parcurgere[i]]);
// debug(mp[C.parcurgere[i]]);
for(auto x : queries[i]){
int c = x.second;
if(c < 0)
c = -1;
else
c = 1;
rez[c * x.second] += c * aib.query(x.first);
}
}
for(i = 0; i < Q; i++){
rez[i] = (rez[i + 1] > 0);
}
return rez;
}
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 Q = S.size();
vector<int> A(Q);
int i;
for(i = 0; i < X.size(); i++) {
init[X[i] + 1].push_back(Y[i] + 1);
init[Y[i] + 1].push_back(X[i] + 1);
}
C.Init(N);
D.Init(N);
for(int i = N; i >= 1; i--) {
for(auto x : init[i]) {
if(x > i) {
C.merge(x, i);
// break;
}
}
}
for(int i = 1; i <= N; i++) {
for(auto x : init[i]) {
if(x < i) {
D.merge(x, i);
// break;
}
}
}
C.DFS(1, 0);
//debug(N);
D.DFS(N, 0);
C.Precalc();
D.Precalc();
for(i = 0; i < Q; i++) {
S[i]++;
R[i]++;
E[i]++;
L[i]++;
int r = S[i], pas = nr_of_bits - 1;
while(pas >= 0) {
int nou = C.dp[r][pas];
if(nou != 0 && nou >= L[i])
r = nou;
pas--;
}
if(r < L[i])
continue;
pii a = {C.timp[r].first, C.timp[r].second};
r = E[i], pas = nr_of_bits - 1;
while(pas >= 0) {
int nou = D.dp[r][pas];
if(nou != 0 && nou <= R[i])
r = nou;
pas--;
}
if(r > R[i])
continue;
pii b = {D.timp[r].first, D.timp[r].second};
int x1 = a.first, x2 = a.second, y1 = b.first, y2 = b.second;
queries[x1 - 1].push_back({y1 - 1, i + 1});
queries[x1 - 1].push_back({y2, -i - 1});
queries[x2].push_back({y2, i + 1});
queries[x2].push_back({y1 - 1, -i - 1});
}
A = Compute(Q);
A.pop_back();
return A;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> Compute(int)':
werewolf.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i = 1; i < D.parcurgere.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~~
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:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(i = 0; i < X.size(); i++) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
25452 KB |
Output is correct |
2 |
Correct |
17 ms |
25452 KB |
Output is correct |
3 |
Correct |
17 ms |
25452 KB |
Output is correct |
4 |
Correct |
17 ms |
25452 KB |
Output is correct |
5 |
Correct |
17 ms |
25396 KB |
Output is correct |
6 |
Correct |
17 ms |
25452 KB |
Output is correct |
7 |
Correct |
17 ms |
25452 KB |
Output is correct |
8 |
Correct |
17 ms |
25452 KB |
Output is correct |
9 |
Correct |
18 ms |
25452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
25452 KB |
Output is correct |
2 |
Correct |
17 ms |
25452 KB |
Output is correct |
3 |
Correct |
17 ms |
25452 KB |
Output is correct |
4 |
Correct |
17 ms |
25452 KB |
Output is correct |
5 |
Correct |
17 ms |
25396 KB |
Output is correct |
6 |
Correct |
17 ms |
25452 KB |
Output is correct |
7 |
Correct |
17 ms |
25452 KB |
Output is correct |
8 |
Correct |
17 ms |
25452 KB |
Output is correct |
9 |
Correct |
18 ms |
25452 KB |
Output is correct |
10 |
Correct |
25 ms |
26972 KB |
Output is correct |
11 |
Correct |
24 ms |
26848 KB |
Output is correct |
12 |
Correct |
24 ms |
26860 KB |
Output is correct |
13 |
Correct |
25 ms |
27100 KB |
Output is correct |
14 |
Correct |
24 ms |
27104 KB |
Output is correct |
15 |
Correct |
25 ms |
27108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1114 ms |
114308 KB |
Output is correct |
2 |
Correct |
912 ms |
124760 KB |
Output is correct |
3 |
Correct |
798 ms |
119896 KB |
Output is correct |
4 |
Correct |
808 ms |
117848 KB |
Output is correct |
5 |
Correct |
820 ms |
117976 KB |
Output is correct |
6 |
Correct |
992 ms |
120020 KB |
Output is correct |
7 |
Correct |
985 ms |
116820 KB |
Output is correct |
8 |
Correct |
853 ms |
124628 KB |
Output is correct |
9 |
Correct |
681 ms |
117980 KB |
Output is correct |
10 |
Correct |
667 ms |
117720 KB |
Output is correct |
11 |
Correct |
693 ms |
117592 KB |
Output is correct |
12 |
Correct |
803 ms |
116044 KB |
Output is correct |
13 |
Correct |
945 ms |
123600 KB |
Output is correct |
14 |
Correct |
943 ms |
123724 KB |
Output is correct |
15 |
Correct |
953 ms |
123716 KB |
Output is correct |
16 |
Correct |
958 ms |
123908 KB |
Output is correct |
17 |
Correct |
970 ms |
116944 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
25452 KB |
Output is correct |
2 |
Correct |
17 ms |
25452 KB |
Output is correct |
3 |
Correct |
17 ms |
25452 KB |
Output is correct |
4 |
Correct |
17 ms |
25452 KB |
Output is correct |
5 |
Correct |
17 ms |
25396 KB |
Output is correct |
6 |
Correct |
17 ms |
25452 KB |
Output is correct |
7 |
Correct |
17 ms |
25452 KB |
Output is correct |
8 |
Correct |
17 ms |
25452 KB |
Output is correct |
9 |
Correct |
18 ms |
25452 KB |
Output is correct |
10 |
Correct |
25 ms |
26972 KB |
Output is correct |
11 |
Correct |
24 ms |
26848 KB |
Output is correct |
12 |
Correct |
24 ms |
26860 KB |
Output is correct |
13 |
Correct |
25 ms |
27100 KB |
Output is correct |
14 |
Correct |
24 ms |
27104 KB |
Output is correct |
15 |
Correct |
25 ms |
27108 KB |
Output is correct |
16 |
Correct |
1114 ms |
114308 KB |
Output is correct |
17 |
Correct |
912 ms |
124760 KB |
Output is correct |
18 |
Correct |
798 ms |
119896 KB |
Output is correct |
19 |
Correct |
808 ms |
117848 KB |
Output is correct |
20 |
Correct |
820 ms |
117976 KB |
Output is correct |
21 |
Correct |
992 ms |
120020 KB |
Output is correct |
22 |
Correct |
985 ms |
116820 KB |
Output is correct |
23 |
Correct |
853 ms |
124628 KB |
Output is correct |
24 |
Correct |
681 ms |
117980 KB |
Output is correct |
25 |
Correct |
667 ms |
117720 KB |
Output is correct |
26 |
Correct |
693 ms |
117592 KB |
Output is correct |
27 |
Correct |
803 ms |
116044 KB |
Output is correct |
28 |
Correct |
945 ms |
123600 KB |
Output is correct |
29 |
Correct |
943 ms |
123724 KB |
Output is correct |
30 |
Correct |
953 ms |
123716 KB |
Output is correct |
31 |
Correct |
958 ms |
123908 KB |
Output is correct |
32 |
Correct |
970 ms |
116944 KB |
Output is correct |
33 |
Correct |
1157 ms |
121420 KB |
Output is correct |
34 |
Correct |
371 ms |
66752 KB |
Output is correct |
35 |
Correct |
1191 ms |
124248 KB |
Output is correct |
36 |
Correct |
1127 ms |
120820 KB |
Output is correct |
37 |
Correct |
1168 ms |
123612 KB |
Output is correct |
38 |
Correct |
1127 ms |
121432 KB |
Output is correct |
39 |
Correct |
1069 ms |
132828 KB |
Output is correct |
40 |
Correct |
1107 ms |
124108 KB |
Output is correct |
41 |
Correct |
1081 ms |
121612 KB |
Output is correct |
42 |
Correct |
913 ms |
117180 KB |
Output is correct |
43 |
Correct |
1209 ms |
127244 KB |
Output is correct |
44 |
Correct |
1094 ms |
123556 KB |
Output is correct |
45 |
Correct |
886 ms |
130888 KB |
Output is correct |
46 |
Correct |
909 ms |
132056 KB |
Output is correct |
47 |
Correct |
950 ms |
123932 KB |
Output is correct |
48 |
Correct |
931 ms |
123856 KB |
Output is correct |
49 |
Correct |
961 ms |
123972 KB |
Output is correct |
50 |
Correct |
950 ms |
123968 KB |
Output is correct |
51 |
Correct |
1008 ms |
125416 KB |
Output is correct |
52 |
Correct |
1012 ms |
125168 KB |
Output is correct |