#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;
const int MAXN = 2e5 + 5, MAXQ = 2e5 + 5, MAXLGN = 20;
int UF[2][MAXN], PAR[2][MAXLGN][MAXN], PRE[2][MAXN], POST[2][MAXN], VERT[2][MAXN], BIT[MAXN], ANS[MAXQ], cur;
vector<int> ADJ[MAXN], TR[2][MAXN];
vector<pii> ADD[MAXN], SUB[MAXN];
int find(int i, int v) {
return UF[i][v] < 0 ? v : UF[i][v] = find(i, UF[i][v]);
}
void join(int i, int v, int w) {
v = find(i, v);
w = find(i, w);
if (v == w) return;
UF[i][w] = v;
TR[i][v].pb(w);
PAR[i][0][w] = v;
}
void dfs(int i, int v) {
VERT[i][PRE[i][v] = ++cur] = v;
FORE(w, TR[i][v]) dfs(i, w);
POST[i][v] = cur;
}
void update(int i, int v) {
for (; i < MAXN; i += i & -i) BIT[i] += v;
}
int rsq(int i) {
int ret = 0;
for (; i > 0; i -= i & -i) ret += BIT[i];
return ret;
}
int rsq(int a, int b) {
return rsq(b) - rsq(a - 1);
}
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(i, sz(X)) {
ADJ[X[i]].pb(Y[i]);
ADJ[Y[i]].pb(X[i]);
}
FOR(i, 2) fill(UF[i], UF[i] + MAXN, -1);
PAR[0][0][0] = 0;
REV(i, N - 1) FORE(j, ADJ[i]) if (i < j) join(0, i, j);
PAR[1][0][N - 1] = N - 1;
FOR(i, N) FORE(j, ADJ[i]) if (i > j) join(1, i, j);
cur = 0;
dfs(0, 0);
cur = 0;
dfs(1, N - 1);
FOR(i, 2) For(j, 1, MAXLGN) FOR(k, N) PAR[i][j][k] = PAR[i][j - 1][PAR[i][j - 1][k]];
FOR(i, sz(S)) {
int s = S[i], e = E[i];
REV(j, MAXLGN - 1) {
if (PAR[0][j][s] >= L[i]) s = PAR[0][j][s];
if (PAR[1][j][e] <= R[i]) e = PAR[1][j][e];
}
ADD[POST[1][e]].eb(s, i);
SUB[PRE[1][e] - 1].eb(s, i);
}
fill(BIT, BIT + MAXN, 0);
fill(ANS, ANS + MAXQ, 0);
For(i, 1, N + 1) {
update(PRE[0][VERT[1][i]], 1);
FORE(q, ADD[i]) ANS[q.s] += rsq(PRE[0][q.f], POST[0][q.f]);
FORE(q, SUB[i]) ANS[q.s] -= rsq(PRE[0][q.f], POST[0][q.f]);
}
vector<int> ret;
FOR(i, sz(S)) ret.pb(ANS[i] > 0);
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
27256 KB |
Output is correct |
2 |
Correct |
27 ms |
27260 KB |
Output is correct |
3 |
Correct |
27 ms |
27468 KB |
Output is correct |
4 |
Correct |
28 ms |
27468 KB |
Output is correct |
5 |
Correct |
27 ms |
27512 KB |
Output is correct |
6 |
Correct |
26 ms |
27512 KB |
Output is correct |
7 |
Correct |
27 ms |
27512 KB |
Output is correct |
8 |
Correct |
27 ms |
27512 KB |
Output is correct |
9 |
Correct |
26 ms |
27612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
27256 KB |
Output is correct |
2 |
Correct |
27 ms |
27260 KB |
Output is correct |
3 |
Correct |
27 ms |
27468 KB |
Output is correct |
4 |
Correct |
28 ms |
27468 KB |
Output is correct |
5 |
Correct |
27 ms |
27512 KB |
Output is correct |
6 |
Correct |
26 ms |
27512 KB |
Output is correct |
7 |
Correct |
27 ms |
27512 KB |
Output is correct |
8 |
Correct |
27 ms |
27512 KB |
Output is correct |
9 |
Correct |
26 ms |
27612 KB |
Output is correct |
10 |
Correct |
34 ms |
28520 KB |
Output is correct |
11 |
Correct |
33 ms |
28560 KB |
Output is correct |
12 |
Correct |
34 ms |
28560 KB |
Output is correct |
13 |
Correct |
35 ms |
28704 KB |
Output is correct |
14 |
Correct |
33 ms |
28708 KB |
Output is correct |
15 |
Correct |
34 ms |
28708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1295 ms |
103456 KB |
Output is correct |
2 |
Correct |
1168 ms |
114420 KB |
Output is correct |
3 |
Correct |
1150 ms |
119832 KB |
Output is correct |
4 |
Correct |
1146 ms |
127284 KB |
Output is correct |
5 |
Correct |
1082 ms |
135652 KB |
Output is correct |
6 |
Correct |
1229 ms |
144772 KB |
Output is correct |
7 |
Correct |
1064 ms |
144940 KB |
Output is correct |
8 |
Correct |
938 ms |
149012 KB |
Output is correct |
9 |
Correct |
631 ms |
149012 KB |
Output is correct |
10 |
Correct |
522 ms |
152644 KB |
Output is correct |
11 |
Correct |
579 ms |
158676 KB |
Output is correct |
12 |
Correct |
560 ms |
166680 KB |
Output is correct |
13 |
Correct |
995 ms |
185144 KB |
Output is correct |
14 |
Correct |
1000 ms |
193588 KB |
Output is correct |
15 |
Correct |
1016 ms |
197124 KB |
Output is correct |
16 |
Correct |
1004 ms |
197128 KB |
Output is correct |
17 |
Correct |
1169 ms |
197128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
27256 KB |
Output is correct |
2 |
Correct |
27 ms |
27260 KB |
Output is correct |
3 |
Correct |
27 ms |
27468 KB |
Output is correct |
4 |
Correct |
28 ms |
27468 KB |
Output is correct |
5 |
Correct |
27 ms |
27512 KB |
Output is correct |
6 |
Correct |
26 ms |
27512 KB |
Output is correct |
7 |
Correct |
27 ms |
27512 KB |
Output is correct |
8 |
Correct |
27 ms |
27512 KB |
Output is correct |
9 |
Correct |
26 ms |
27612 KB |
Output is correct |
10 |
Correct |
34 ms |
28520 KB |
Output is correct |
11 |
Correct |
33 ms |
28560 KB |
Output is correct |
12 |
Correct |
34 ms |
28560 KB |
Output is correct |
13 |
Correct |
35 ms |
28704 KB |
Output is correct |
14 |
Correct |
33 ms |
28708 KB |
Output is correct |
15 |
Correct |
34 ms |
28708 KB |
Output is correct |
16 |
Correct |
1295 ms |
103456 KB |
Output is correct |
17 |
Correct |
1168 ms |
114420 KB |
Output is correct |
18 |
Correct |
1150 ms |
119832 KB |
Output is correct |
19 |
Correct |
1146 ms |
127284 KB |
Output is correct |
20 |
Correct |
1082 ms |
135652 KB |
Output is correct |
21 |
Correct |
1229 ms |
144772 KB |
Output is correct |
22 |
Correct |
1064 ms |
144940 KB |
Output is correct |
23 |
Correct |
938 ms |
149012 KB |
Output is correct |
24 |
Correct |
631 ms |
149012 KB |
Output is correct |
25 |
Correct |
522 ms |
152644 KB |
Output is correct |
26 |
Correct |
579 ms |
158676 KB |
Output is correct |
27 |
Correct |
560 ms |
166680 KB |
Output is correct |
28 |
Correct |
995 ms |
185144 KB |
Output is correct |
29 |
Correct |
1000 ms |
193588 KB |
Output is correct |
30 |
Correct |
1016 ms |
197124 KB |
Output is correct |
31 |
Correct |
1004 ms |
197128 KB |
Output is correct |
32 |
Correct |
1169 ms |
197128 KB |
Output is correct |
33 |
Correct |
1342 ms |
197128 KB |
Output is correct |
34 |
Correct |
390 ms |
197128 KB |
Output is correct |
35 |
Correct |
1285 ms |
212396 KB |
Output is correct |
36 |
Correct |
1355 ms |
218508 KB |
Output is correct |
37 |
Correct |
1392 ms |
228796 KB |
Output is correct |
38 |
Correct |
1341 ms |
236376 KB |
Output is correct |
39 |
Correct |
1185 ms |
253596 KB |
Output is correct |
40 |
Correct |
956 ms |
260656 KB |
Output is correct |
41 |
Correct |
694 ms |
263224 KB |
Output is correct |
42 |
Correct |
560 ms |
270332 KB |
Output is correct |
43 |
Correct |
944 ms |
288236 KB |
Output is correct |
44 |
Correct |
928 ms |
288236 KB |
Output is correct |
45 |
Correct |
719 ms |
297016 KB |
Output is correct |
46 |
Correct |
886 ms |
297016 KB |
Output is correct |
47 |
Correct |
1172 ms |
297016 KB |
Output is correct |
48 |
Correct |
1188 ms |
297016 KB |
Output is correct |
49 |
Correct |
1034 ms |
297016 KB |
Output is correct |
50 |
Correct |
1044 ms |
297016 KB |
Output is correct |
51 |
Correct |
926 ms |
297016 KB |
Output is correct |
52 |
Correct |
895 ms |
297016 KB |
Output is correct |