#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
const int maxn = 2e5+5;
struct dsu
{
vector<int> par;
dsu(int n = 0)
{
par.resize(n);
for(int i = 0; i< n; i++) par[i] = i;
}
int findset(int x)
{
if(x == par[x]) return x;
return par[x] = findset(par[x]);
}
};
dsu hum, wolf;
int n, m, q;
vector<int> adj[maxn];
struct tahm
{
int s, e, l, r, id;
int hum, wolf;
tahm(int s, int e, int l, int r, int id): s(s), e(e), l(l), r(r), id(id) {}
};
bool cmpl(tahm a, tahm b)
{
return a.l< b.l;
}
bool cmpr(tahm a, tahm b)
{
return a.r< b.r;
}
vector<tahm> kench;
vector<int> twolf[2*maxn];
vector<int> thum[2*maxn];
vector<int> pred;
int numb[maxn];
int lb[2*maxn];
int rb[2*maxn];
void dfs(int u = 2*n-2)
{
if(u< n) pred.pb(u);
for(int v : twolf[u]) dfs(v);
}
void calc(int u = 2*n-2)
{
lb[u] = 1e9, rb[u] = -1;
if(u< n) lb[u] = rb[u] = numb[u];
for(int v : twolf[u])
{
calc(v);
lb[u] = min(lb[u], lb[v]);
rb[u] = max(rb[u], rb[v]);
}
// printf("lb[%d] = %d, rb[%d] = %d\n", u, lb[u], u, rb[u]);
}
set<int> roots[2*maxn];
vector<int> elems[2*maxn];
vector<tahm> want[2*maxn];
vector<int> ans;
void comb(int u = 2*n-2)
{
if(u< n)
{
roots[u].insert(numb[u]);
elems[u].pb(numb[u]);
}
ii big = {0, -1};
for(int v : thum[u])
{
comb(v);
big = max(big, {(int) elems[v].size(), v});
}
if(big.Y != -1)
{
swap(roots[u], roots[big.Y]);
swap(elems[u], elems[big.Y]);
for(int v : thum[u])
{
for(int x : elems[v])
{
roots[u].insert(x);
elems[u].pb(x);
}
}
}
for(tahm kk : want[u])
{
int id = kk.id;
int wolf = kk.wolf;
int lo = lb[wolf], hi = rb[wolf];
ans[id] = roots[u].upper_bound(hi) != roots[u].upper_bound(lo-1);
}
}
vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R)
{
n = N;
m = X.size();
q = S.size();
for(int i = 0; i< q; i++) kench.pb(tahm(S[i], E[i], L[i], R[i], i));
for(int i = 0; i< m; i++)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
wolf = dsu(2*n);
sort(kench.begin(), kench.end(), cmpr);
int pt = 0;
int cnt = n;
for(int i = 0; i< n; i++)
{
for(int v : adj[i])
{
if(v< i)
{
int a = wolf.findset(i);
int b = wolf.findset(v);
if(a == b) continue;
wolf.par[a] = wolf.par[b] = cnt;
twolf[cnt].pb(a);
twolf[cnt].pb(b);
// printf("%d-->%d %d-->%d\n", cnt, a, cnt, b);
cnt++;
}
}
while(pt< q && kench[pt].r == i)
{
int e = kench[pt].e;
int pp = wolf.findset(e);
kench[pt].wolf = pp;
pt++;
}
}
// printf("finished wolf\n");
hum = dsu(2*n);
sort(kench.begin(), kench.end(), cmpl);
reverse(kench.begin(), kench.end());
pt = 0;
cnt = n;
for(int i = n-1; i>= 0; i--)
{
for(int v : adj[i])
{
if(v> i)
{
int a = hum.findset(v);
int b = hum.findset(i);
if(a == b) continue;
hum.par[a] = hum.par[b] = cnt;
// printf("%d->%d, %d->%d\n", cnt, a, cnt, b);
thum[cnt].pb(a);
thum[cnt].pb(b);
cnt++;
}
}
while(pt< q && kench[pt].l == i)
{
int s = kench[pt].s;
int pp = hum.findset(s);
kench[pt].hum = pp;
pt++;
}
}
dfs();
// for(int i = 0; i< n; i++) printf("%d ", pred[i]);
// printf("\n");
for(int i = 0; i< n; i++) numb[pred[i]] = i;
calc();
// printf("finished renumbering\n");
ans.resize(q);
for(int i = 0; i< q; i++)
{
int wolf = kench[i].wolf, hum = kench[i].hum;
want[kench[i].hum].pb(kench[i]);
}
comb();
// printf("%d\n", roots[2*n-2]->ask(0, n-1));
return ans;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:204:7: warning: unused variable 'wolf' [-Wunused-variable]
int wolf = kench[i].wolf, hum = kench[i].hum;
^~~~
werewolf.cpp:204:29: warning: unused variable 'hum' [-Wunused-variable]
int wolf = kench[i].wolf, hum = kench[i].hum;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
61432 KB |
Output is correct |
2 |
Correct |
53 ms |
61432 KB |
Output is correct |
3 |
Correct |
53 ms |
61432 KB |
Output is correct |
4 |
Correct |
53 ms |
61432 KB |
Output is correct |
5 |
Correct |
52 ms |
61432 KB |
Output is correct |
6 |
Correct |
53 ms |
61432 KB |
Output is correct |
7 |
Correct |
52 ms |
61400 KB |
Output is correct |
8 |
Correct |
55 ms |
61404 KB |
Output is correct |
9 |
Correct |
57 ms |
61432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
61432 KB |
Output is correct |
2 |
Correct |
53 ms |
61432 KB |
Output is correct |
3 |
Correct |
53 ms |
61432 KB |
Output is correct |
4 |
Correct |
53 ms |
61432 KB |
Output is correct |
5 |
Correct |
52 ms |
61432 KB |
Output is correct |
6 |
Correct |
53 ms |
61432 KB |
Output is correct |
7 |
Correct |
52 ms |
61400 KB |
Output is correct |
8 |
Correct |
55 ms |
61404 KB |
Output is correct |
9 |
Correct |
57 ms |
61432 KB |
Output is correct |
10 |
Correct |
69 ms |
63004 KB |
Output is correct |
11 |
Correct |
65 ms |
63004 KB |
Output is correct |
12 |
Correct |
64 ms |
63224 KB |
Output is correct |
13 |
Correct |
63 ms |
62992 KB |
Output is correct |
14 |
Correct |
64 ms |
63096 KB |
Output is correct |
15 |
Correct |
63 ms |
63096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1309 ms |
189956 KB |
Output is correct |
2 |
Correct |
1054 ms |
164112 KB |
Output is correct |
3 |
Correct |
1094 ms |
172380 KB |
Output is correct |
4 |
Correct |
1191 ms |
187720 KB |
Output is correct |
5 |
Correct |
1211 ms |
191044 KB |
Output is correct |
6 |
Correct |
1236 ms |
197324 KB |
Output is correct |
7 |
Correct |
1372 ms |
199600 KB |
Output is correct |
8 |
Correct |
1160 ms |
163932 KB |
Output is correct |
9 |
Correct |
951 ms |
170752 KB |
Output is correct |
10 |
Correct |
1096 ms |
187400 KB |
Output is correct |
11 |
Correct |
1115 ms |
188848 KB |
Output is correct |
12 |
Correct |
1200 ms |
195164 KB |
Output is correct |
13 |
Correct |
973 ms |
167328 KB |
Output is correct |
14 |
Correct |
1000 ms |
167420 KB |
Output is correct |
15 |
Correct |
959 ms |
167512 KB |
Output is correct |
16 |
Correct |
959 ms |
167372 KB |
Output is correct |
17 |
Correct |
1342 ms |
197440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
61432 KB |
Output is correct |
2 |
Correct |
53 ms |
61432 KB |
Output is correct |
3 |
Correct |
53 ms |
61432 KB |
Output is correct |
4 |
Correct |
53 ms |
61432 KB |
Output is correct |
5 |
Correct |
52 ms |
61432 KB |
Output is correct |
6 |
Correct |
53 ms |
61432 KB |
Output is correct |
7 |
Correct |
52 ms |
61400 KB |
Output is correct |
8 |
Correct |
55 ms |
61404 KB |
Output is correct |
9 |
Correct |
57 ms |
61432 KB |
Output is correct |
10 |
Correct |
69 ms |
63004 KB |
Output is correct |
11 |
Correct |
65 ms |
63004 KB |
Output is correct |
12 |
Correct |
64 ms |
63224 KB |
Output is correct |
13 |
Correct |
63 ms |
62992 KB |
Output is correct |
14 |
Correct |
64 ms |
63096 KB |
Output is correct |
15 |
Correct |
63 ms |
63096 KB |
Output is correct |
16 |
Correct |
1309 ms |
189956 KB |
Output is correct |
17 |
Correct |
1054 ms |
164112 KB |
Output is correct |
18 |
Correct |
1094 ms |
172380 KB |
Output is correct |
19 |
Correct |
1191 ms |
187720 KB |
Output is correct |
20 |
Correct |
1211 ms |
191044 KB |
Output is correct |
21 |
Correct |
1236 ms |
197324 KB |
Output is correct |
22 |
Correct |
1372 ms |
199600 KB |
Output is correct |
23 |
Correct |
1160 ms |
163932 KB |
Output is correct |
24 |
Correct |
951 ms |
170752 KB |
Output is correct |
25 |
Correct |
1096 ms |
187400 KB |
Output is correct |
26 |
Correct |
1115 ms |
188848 KB |
Output is correct |
27 |
Correct |
1200 ms |
195164 KB |
Output is correct |
28 |
Correct |
973 ms |
167328 KB |
Output is correct |
29 |
Correct |
1000 ms |
167420 KB |
Output is correct |
30 |
Correct |
959 ms |
167512 KB |
Output is correct |
31 |
Correct |
959 ms |
167372 KB |
Output is correct |
32 |
Correct |
1342 ms |
197440 KB |
Output is correct |
33 |
Correct |
1279 ms |
169404 KB |
Output is correct |
34 |
Correct |
389 ms |
106204 KB |
Output is correct |
35 |
Correct |
1367 ms |
168792 KB |
Output is correct |
36 |
Correct |
1324 ms |
169844 KB |
Output is correct |
37 |
Correct |
1470 ms |
167736 KB |
Output is correct |
38 |
Correct |
1635 ms |
168808 KB |
Output is correct |
39 |
Correct |
1351 ms |
178540 KB |
Output is correct |
40 |
Correct |
1229 ms |
171484 KB |
Output is correct |
41 |
Correct |
1232 ms |
166236 KB |
Output is correct |
42 |
Correct |
1185 ms |
167900 KB |
Output is correct |
43 |
Correct |
1499 ms |
173428 KB |
Output is correct |
44 |
Correct |
1374 ms |
167516 KB |
Output is correct |
45 |
Correct |
1303 ms |
168528 KB |
Output is correct |
46 |
Correct |
1367 ms |
178964 KB |
Output is correct |
47 |
Correct |
996 ms |
167688 KB |
Output is correct |
48 |
Correct |
956 ms |
167444 KB |
Output is correct |
49 |
Correct |
994 ms |
167544 KB |
Output is correct |
50 |
Correct |
1008 ms |
167484 KB |
Output is correct |
51 |
Correct |
1356 ms |
172108 KB |
Output is correct |
52 |
Correct |
1342 ms |
172120 KB |
Output is correct |