#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define lb lower_bound
const int N=1000006, INF=1e9+7;
int p[N], p2[N], f[N];
vector<vi> Ans;
struct abc{
set<pii> s;
set<int> k;
queue<int> d;
int pa;
vi v;
int sz;
} e[N];
void add_key(int x, int c){
auto &[s, k, d, pa, v, sz] = e[x];
if(k.find(c)!=k.end()) return;
k.insert(c);
for (auto it = s.lb({c,0}); it != s.lb({c,INF}); it=s.lb({c, 0}))
d.push((*it).second), s.erase(it);
}
void add_door(int x, int y, int c){
auto &[s, k, d, pa, v, sz] = e[x];
if(k.find(c)!=k.end()) d.push(y);
else s.insert({c, y});
}
int P(int x){ return (p[x]<0) ? x : p[x] = P(p[x]); }
int sz(int x){ return -P(x); }
void unite(int x, int y){
if((x=P(x))==(y=P(y)))return;
if(sz(x)<sz(y))swap(x, y);
p[x]+=p[y];
p[y]=x;
}
int P2(int x){ return (p2[x]<0) ? x : p2[x] = P2(p2[x]); }
int sz2(int x){ return -P2(x); }
void unite2(int x, int y){
if((x=P2(x))==(y=P2(y)))return;
if(sz2(x)<sz2(y))swap(x, y);
p2[x]+=p2[y];
p2[y]=x;
}
void un(int x, int y){
int PA=e[y].pa;
unite2(x, y);
if(e[x].sz<e[y].sz)swap(e[x], e[y]);
if(P2(x)==y)swap(e[x], e[y]), swap(x, y);
auto &[xs, xk, xd, xpa, xv, xsz]=e[x];
auto &[ys, yk, yd, ypa, yv, ysz]=e[y];
for (auto [k,Y]:ys) add_door(x, Y, k);
for (auto k:yk) add_key(x, k);
while(!yd.empty()) xd.push(yd.front()), yd.pop();
xpa=PA;
for (auto Y:yv) xv.pb(Y);
xsz=xv.size();
}
void next(int x, int w=-1){
int X=P2(x), PA;
auto &[s, k, d, pa, v, sz]=e[X];
if(!d.empty()){
pa=d.front();
d.pop();
PA=P2(pa);
while(PA==X && !d.empty()){
pa=d.front();
d.pop();
PA=P2(pa);
}
}
if(pa==-1 || PA==X){
Ans.pb(v);
f[P(X)]=1;
return;
}
if(P(X)==P(PA)){
while(PA!=X)un(X, PA), X=P2(x), PA=P2(e[X].pa);
e[X].pa=-1;
next(X);
}else{
if(f[P(PA)])f[P(X)]=1;
unite(X, PA);
}
}
vi find_reachable(vi r, vi u, vi v, vi c) {
vi ans(r.size(), 0);
int n=r.size(), m=u.size();
vector<pii> V[n];
for (int i=0; i<m; i++){
int x=u[i], y=v[i], k=c[i];
V[x].pb({y, k});
V[y].pb({x, k});
}
for (int i=0; i<n; i++){
p[i]=p2[i]=-1;
for (auto[y,c]:V[i])e[i].s.insert({c, y});
add_key(i, r[i]);
e[i].pa=-1;
e[i].v.pb(i);
e[i].sz=1;
}
for (int i=0; i<n; i++)
if(f[P(i)]==0 && e[P2(i)].pa==-1)next(i);
int an=INF;
for (auto v:Ans)an=min(an, (int)v.size());
for (auto v:Ans){
if(an<v.size())continue;
for (auto x:v) ans[x]=1;
}
return ans;
}
Compilation message
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:122:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | if(an<v.size())continue;
| ~~^~~~~~~~~
keys.cpp: In function 'void next(int, int)':
keys.cpp:93:14: warning: 'PA' may be used uninitialized in this function [-Wmaybe-uninitialized]
93 | unite(X, PA);
| ~~~~~^~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
493 ms |
806568 KB |
Output is correct |
2 |
Correct |
501 ms |
806572 KB |
Output is correct |
3 |
Correct |
482 ms |
806576 KB |
Output is correct |
4 |
Correct |
602 ms |
806536 KB |
Output is correct |
5 |
Correct |
519 ms |
806576 KB |
Output is correct |
6 |
Correct |
475 ms |
806452 KB |
Output is correct |
7 |
Correct |
466 ms |
806484 KB |
Output is correct |
8 |
Correct |
448 ms |
806596 KB |
Output is correct |
9 |
Correct |
458 ms |
806696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
493 ms |
806568 KB |
Output is correct |
2 |
Correct |
501 ms |
806572 KB |
Output is correct |
3 |
Correct |
482 ms |
806576 KB |
Output is correct |
4 |
Correct |
602 ms |
806536 KB |
Output is correct |
5 |
Correct |
519 ms |
806576 KB |
Output is correct |
6 |
Correct |
475 ms |
806452 KB |
Output is correct |
7 |
Correct |
466 ms |
806484 KB |
Output is correct |
8 |
Correct |
448 ms |
806596 KB |
Output is correct |
9 |
Correct |
458 ms |
806696 KB |
Output is correct |
10 |
Correct |
469 ms |
806620 KB |
Output is correct |
11 |
Correct |
488 ms |
806628 KB |
Output is correct |
12 |
Correct |
491 ms |
806704 KB |
Output is correct |
13 |
Correct |
439 ms |
806472 KB |
Output is correct |
14 |
Correct |
522 ms |
806556 KB |
Output is correct |
15 |
Correct |
425 ms |
806616 KB |
Output is correct |
16 |
Correct |
458 ms |
806464 KB |
Output is correct |
17 |
Correct |
450 ms |
806572 KB |
Output is correct |
18 |
Correct |
445 ms |
806592 KB |
Output is correct |
19 |
Correct |
440 ms |
806528 KB |
Output is correct |
20 |
Correct |
444 ms |
806616 KB |
Output is correct |
21 |
Correct |
459 ms |
806504 KB |
Output is correct |
22 |
Correct |
615 ms |
806588 KB |
Output is correct |
23 |
Correct |
628 ms |
806644 KB |
Output is correct |
24 |
Correct |
501 ms |
806652 KB |
Output is correct |
25 |
Correct |
554 ms |
806600 KB |
Output is correct |
26 |
Correct |
428 ms |
806620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
493 ms |
806568 KB |
Output is correct |
2 |
Correct |
501 ms |
806572 KB |
Output is correct |
3 |
Correct |
482 ms |
806576 KB |
Output is correct |
4 |
Correct |
602 ms |
806536 KB |
Output is correct |
5 |
Correct |
519 ms |
806576 KB |
Output is correct |
6 |
Correct |
475 ms |
806452 KB |
Output is correct |
7 |
Correct |
466 ms |
806484 KB |
Output is correct |
8 |
Correct |
448 ms |
806596 KB |
Output is correct |
9 |
Correct |
458 ms |
806696 KB |
Output is correct |
10 |
Correct |
469 ms |
806620 KB |
Output is correct |
11 |
Correct |
488 ms |
806628 KB |
Output is correct |
12 |
Correct |
491 ms |
806704 KB |
Output is correct |
13 |
Correct |
439 ms |
806472 KB |
Output is correct |
14 |
Correct |
522 ms |
806556 KB |
Output is correct |
15 |
Correct |
425 ms |
806616 KB |
Output is correct |
16 |
Correct |
458 ms |
806464 KB |
Output is correct |
17 |
Correct |
450 ms |
806572 KB |
Output is correct |
18 |
Correct |
445 ms |
806592 KB |
Output is correct |
19 |
Correct |
440 ms |
806528 KB |
Output is correct |
20 |
Correct |
444 ms |
806616 KB |
Output is correct |
21 |
Correct |
459 ms |
806504 KB |
Output is correct |
22 |
Correct |
615 ms |
806588 KB |
Output is correct |
23 |
Correct |
628 ms |
806644 KB |
Output is correct |
24 |
Correct |
501 ms |
806652 KB |
Output is correct |
25 |
Correct |
554 ms |
806600 KB |
Output is correct |
26 |
Correct |
428 ms |
806620 KB |
Output is correct |
27 |
Correct |
638 ms |
807268 KB |
Output is correct |
28 |
Correct |
510 ms |
807092 KB |
Output is correct |
29 |
Correct |
518 ms |
807188 KB |
Output is correct |
30 |
Correct |
517 ms |
806844 KB |
Output is correct |
31 |
Correct |
526 ms |
806872 KB |
Output is correct |
32 |
Correct |
470 ms |
806604 KB |
Output is correct |
33 |
Correct |
480 ms |
806812 KB |
Output is correct |
34 |
Correct |
633 ms |
806840 KB |
Output is correct |
35 |
Correct |
464 ms |
806900 KB |
Output is correct |
36 |
Correct |
429 ms |
806940 KB |
Output is correct |
37 |
Correct |
504 ms |
807108 KB |
Output is correct |
38 |
Correct |
421 ms |
807108 KB |
Output is correct |
39 |
Correct |
493 ms |
807168 KB |
Output is correct |
40 |
Correct |
427 ms |
806852 KB |
Output is correct |
41 |
Correct |
433 ms |
807032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
493 ms |
806568 KB |
Output is correct |
2 |
Correct |
501 ms |
806572 KB |
Output is correct |
3 |
Correct |
482 ms |
806576 KB |
Output is correct |
4 |
Correct |
602 ms |
806536 KB |
Output is correct |
5 |
Correct |
519 ms |
806576 KB |
Output is correct |
6 |
Correct |
475 ms |
806452 KB |
Output is correct |
7 |
Correct |
466 ms |
806484 KB |
Output is correct |
8 |
Correct |
448 ms |
806596 KB |
Output is correct |
9 |
Correct |
458 ms |
806696 KB |
Output is correct |
10 |
Correct |
851 ms |
867560 KB |
Output is correct |
11 |
Correct |
1101 ms |
894024 KB |
Output is correct |
12 |
Correct |
525 ms |
822400 KB |
Output is correct |
13 |
Correct |
934 ms |
881372 KB |
Output is correct |
14 |
Correct |
807 ms |
867380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
493 ms |
806568 KB |
Output is correct |
2 |
Correct |
501 ms |
806572 KB |
Output is correct |
3 |
Correct |
482 ms |
806576 KB |
Output is correct |
4 |
Correct |
602 ms |
806536 KB |
Output is correct |
5 |
Correct |
519 ms |
806576 KB |
Output is correct |
6 |
Correct |
475 ms |
806452 KB |
Output is correct |
7 |
Correct |
466 ms |
806484 KB |
Output is correct |
8 |
Correct |
448 ms |
806596 KB |
Output is correct |
9 |
Correct |
458 ms |
806696 KB |
Output is correct |
10 |
Correct |
469 ms |
806620 KB |
Output is correct |
11 |
Correct |
488 ms |
806628 KB |
Output is correct |
12 |
Correct |
491 ms |
806704 KB |
Output is correct |
13 |
Correct |
439 ms |
806472 KB |
Output is correct |
14 |
Correct |
522 ms |
806556 KB |
Output is correct |
15 |
Correct |
425 ms |
806616 KB |
Output is correct |
16 |
Correct |
458 ms |
806464 KB |
Output is correct |
17 |
Correct |
450 ms |
806572 KB |
Output is correct |
18 |
Correct |
445 ms |
806592 KB |
Output is correct |
19 |
Correct |
440 ms |
806528 KB |
Output is correct |
20 |
Correct |
444 ms |
806616 KB |
Output is correct |
21 |
Correct |
459 ms |
806504 KB |
Output is correct |
22 |
Correct |
615 ms |
806588 KB |
Output is correct |
23 |
Correct |
628 ms |
806644 KB |
Output is correct |
24 |
Correct |
501 ms |
806652 KB |
Output is correct |
25 |
Correct |
554 ms |
806600 KB |
Output is correct |
26 |
Correct |
428 ms |
806620 KB |
Output is correct |
27 |
Correct |
638 ms |
807268 KB |
Output is correct |
28 |
Correct |
510 ms |
807092 KB |
Output is correct |
29 |
Correct |
518 ms |
807188 KB |
Output is correct |
30 |
Correct |
517 ms |
806844 KB |
Output is correct |
31 |
Correct |
526 ms |
806872 KB |
Output is correct |
32 |
Correct |
470 ms |
806604 KB |
Output is correct |
33 |
Correct |
480 ms |
806812 KB |
Output is correct |
34 |
Correct |
633 ms |
806840 KB |
Output is correct |
35 |
Correct |
464 ms |
806900 KB |
Output is correct |
36 |
Correct |
429 ms |
806940 KB |
Output is correct |
37 |
Correct |
504 ms |
807108 KB |
Output is correct |
38 |
Correct |
421 ms |
807108 KB |
Output is correct |
39 |
Correct |
493 ms |
807168 KB |
Output is correct |
40 |
Correct |
427 ms |
806852 KB |
Output is correct |
41 |
Correct |
433 ms |
807032 KB |
Output is correct |
42 |
Correct |
851 ms |
867560 KB |
Output is correct |
43 |
Correct |
1101 ms |
894024 KB |
Output is correct |
44 |
Correct |
525 ms |
822400 KB |
Output is correct |
45 |
Correct |
934 ms |
881372 KB |
Output is correct |
46 |
Correct |
807 ms |
867380 KB |
Output is correct |
47 |
Correct |
442 ms |
806500 KB |
Output is correct |
48 |
Correct |
440 ms |
806568 KB |
Output is correct |
49 |
Correct |
449 ms |
806572 KB |
Output is correct |
50 |
Correct |
890 ms |
867616 KB |
Output is correct |
51 |
Correct |
815 ms |
866400 KB |
Output is correct |
52 |
Correct |
678 ms |
865376 KB |
Output is correct |
53 |
Correct |
757 ms |
865868 KB |
Output is correct |
54 |
Correct |
708 ms |
865712 KB |
Output is correct |
55 |
Correct |
937 ms |
871500 KB |
Output is correct |
56 |
Correct |
906 ms |
890092 KB |
Output is correct |
57 |
Correct |
1016 ms |
904216 KB |
Output is correct |
58 |
Correct |
852 ms |
877716 KB |
Output is correct |
59 |
Correct |
1178 ms |
884412 KB |
Output is correct |
60 |
Correct |
1105 ms |
884456 KB |
Output is correct |
61 |
Correct |
1086 ms |
885996 KB |
Output is correct |
62 |
Correct |
1459 ms |
947928 KB |
Output is correct |
63 |
Correct |
719 ms |
872988 KB |
Output is correct |
64 |
Correct |
492 ms |
807704 KB |
Output is correct |
65 |
Correct |
515 ms |
807584 KB |
Output is correct |
66 |
Correct |
1489 ms |
947944 KB |
Output is correct |
67 |
Correct |
551 ms |
813124 KB |
Output is correct |
68 |
Correct |
506 ms |
817276 KB |
Output is correct |
69 |
Correct |
1185 ms |
884060 KB |
Output is correct |
70 |
Correct |
536 ms |
827504 KB |
Output is correct |
71 |
Correct |
838 ms |
865596 KB |
Output is correct |
72 |
Correct |
1191 ms |
884060 KB |
Output is correct |
73 |
Correct |
1510 ms |
947848 KB |
Output is correct |