#include "werewolf.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define vll vector<ll>
#define ins insert
#define lb lower_bound
#define ub upper_bound
using namespace std;
const ll N=2e5+5;
const ll inf=1e9;
vector<vll> G(N);
struct dsu{
vector<vll> g;
vll tin, tout;
vll p, pr;
ll tiktak;
ll n;
bool inc;
dsu(ll N, ll f){
n = N;
inc = f;
tiktak = -1;
tin.resize(n);
tout.resize(n);
g.resize(n);
p.resize(n);
for(ll i=0;i<n;i++) p[i] = i;
}
ll anc(ll a){
return (p[a] == a ? a : p[a] = anc(p[a]));
}
bool f(ll a, ll b){
return inc ? a < b : a > b;
}
bool uni(ll a, ll b){
a = anc(a), b = anc(b);
if(a == b) return false;
if(f(a, b)) swap(a, b);
p[b] = a;
g[a].pb(b);
return true;
}
void build(vll s, vll l){
ll i, q = s.size();
pr.resize(q);
vector<vll> qu(n);
for(i=0;i<q;i++){
qu[l[i]].pb(i);
}
if(inc) i = 0;
else i = n - 1;
while(i>=0 && i<n){
for(auto to : G[i]){
if((inc && to < i ) || (!inc && to > i)){
uni(to, i);
}
}
for(auto j : qu[i]){
pr[j] = anc(s[j]);
}
//iteration
i += inc ? 1 : -1;
}
}
void dfs(ll v){
tin[v] = ++tiktak;
for(auto i : g[v]) dfs(i);
tout[v] = tiktak;
}
};
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
ll i;
ll m = X.size();
ll q = S.size();
for(i=0;i<m;i++){
G[X[i]].pb(Y[i]);
G[Y[i]].pb(X[i]);
}
dsu s(n, 0);
dsu t(n, 1);
s.build(S, L);
t.build(E, R);
s.dfs(0);
t.dfs(n-1);
vector<vll> qu(n);
for(i=0;i<q;i++){
qu[s.pr[i]].pb(i);
}
vll ans(q);
vector<set<ll>> st(n);
function<void(int)> dfs = [&](ll v){
st[v].ins(t.tin[v]);
for(auto i : s.g[v]){
dfs(i);
if(st[v].size() < st[i].size()) swap(st[i], st[v]);
for(auto j : st[i]){
st[v].ins(j);
}st[i].clear();
}
for(auto i : qu[v]){
int l = t.tin[t.pr[i]], r = t.tout[t.pr[i]];
ans[i] = (st[v].lb(l) != st[v].ub(r));
}
};
dfs(0);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
6 ms |
6232 KB |
Output is correct |
11 |
Correct |
6 ms |
6128 KB |
Output is correct |
12 |
Correct |
5 ms |
6184 KB |
Output is correct |
13 |
Correct |
6 ms |
6236 KB |
Output is correct |
14 |
Correct |
6 ms |
6236 KB |
Output is correct |
15 |
Correct |
6 ms |
6348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
398 ms |
82148 KB |
Output is correct |
2 |
Correct |
387 ms |
80196 KB |
Output is correct |
3 |
Correct |
394 ms |
78560 KB |
Output is correct |
4 |
Correct |
413 ms |
78556 KB |
Output is correct |
5 |
Correct |
432 ms |
79332 KB |
Output is correct |
6 |
Correct |
405 ms |
80780 KB |
Output is correct |
7 |
Correct |
472 ms |
82076 KB |
Output is correct |
8 |
Correct |
382 ms |
80348 KB |
Output is correct |
9 |
Correct |
382 ms |
78520 KB |
Output is correct |
10 |
Correct |
365 ms |
78276 KB |
Output is correct |
11 |
Correct |
402 ms |
78128 KB |
Output is correct |
12 |
Correct |
375 ms |
79328 KB |
Output is correct |
13 |
Correct |
406 ms |
99616 KB |
Output is correct |
14 |
Correct |
391 ms |
99432 KB |
Output is correct |
15 |
Correct |
344 ms |
99552 KB |
Output is correct |
16 |
Correct |
365 ms |
99512 KB |
Output is correct |
17 |
Correct |
375 ms |
82172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
1 ms |
4956 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
1 ms |
4956 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
1 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
4956 KB |
Output is correct |
10 |
Correct |
6 ms |
6232 KB |
Output is correct |
11 |
Correct |
6 ms |
6128 KB |
Output is correct |
12 |
Correct |
5 ms |
6184 KB |
Output is correct |
13 |
Correct |
6 ms |
6236 KB |
Output is correct |
14 |
Correct |
6 ms |
6236 KB |
Output is correct |
15 |
Correct |
6 ms |
6348 KB |
Output is correct |
16 |
Correct |
398 ms |
82148 KB |
Output is correct |
17 |
Correct |
387 ms |
80196 KB |
Output is correct |
18 |
Correct |
394 ms |
78560 KB |
Output is correct |
19 |
Correct |
413 ms |
78556 KB |
Output is correct |
20 |
Correct |
432 ms |
79332 KB |
Output is correct |
21 |
Correct |
405 ms |
80780 KB |
Output is correct |
22 |
Correct |
472 ms |
82076 KB |
Output is correct |
23 |
Correct |
382 ms |
80348 KB |
Output is correct |
24 |
Correct |
382 ms |
78520 KB |
Output is correct |
25 |
Correct |
365 ms |
78276 KB |
Output is correct |
26 |
Correct |
402 ms |
78128 KB |
Output is correct |
27 |
Correct |
375 ms |
79328 KB |
Output is correct |
28 |
Correct |
406 ms |
99616 KB |
Output is correct |
29 |
Correct |
391 ms |
99432 KB |
Output is correct |
30 |
Correct |
344 ms |
99552 KB |
Output is correct |
31 |
Correct |
365 ms |
99512 KB |
Output is correct |
32 |
Correct |
375 ms |
82172 KB |
Output is correct |
33 |
Correct |
415 ms |
81884 KB |
Output is correct |
34 |
Correct |
162 ms |
39476 KB |
Output is correct |
35 |
Correct |
428 ms |
87444 KB |
Output is correct |
36 |
Correct |
416 ms |
81684 KB |
Output is correct |
37 |
Correct |
455 ms |
85952 KB |
Output is correct |
38 |
Correct |
418 ms |
82912 KB |
Output is correct |
39 |
Correct |
412 ms |
87176 KB |
Output is correct |
40 |
Correct |
414 ms |
96508 KB |
Output is correct |
41 |
Correct |
366 ms |
83360 KB |
Output is correct |
42 |
Correct |
352 ms |
79912 KB |
Output is correct |
43 |
Correct |
493 ms |
93972 KB |
Output is correct |
44 |
Correct |
406 ms |
84716 KB |
Output is correct |
45 |
Correct |
383 ms |
85728 KB |
Output is correct |
46 |
Correct |
390 ms |
85216 KB |
Output is correct |
47 |
Correct |
393 ms |
100316 KB |
Output is correct |
48 |
Correct |
377 ms |
100260 KB |
Output is correct |
49 |
Correct |
370 ms |
100320 KB |
Output is correct |
50 |
Correct |
361 ms |
100064 KB |
Output is correct |
51 |
Correct |
382 ms |
95976 KB |
Output is correct |
52 |
Correct |
374 ms |
95780 KB |
Output is correct |