# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
497453 |
2021-12-23T06:10:05 Z |
David_M |
Keys (IOI21_keys) |
C++17 |
|
1453 ms |
952924 KB |
#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){
//cout<<"BBB"<<" "<<x<<endl;
//for (int i=0; i<4; i++){
// cout<<P(i)<<" "<<P2(i)<<"A"<<endl;
//}
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);
}
}
//cout<<"_"<<x<<" "<<pa<<endl;
if(pa==-1 || PA==X){
//cout<<"LEFJdsifjo"<<endl;
//for (auto E:v)cout<<E<<" ";cout<<endl;
Ans.pb(v);
f[P(X)]=1;
return;
}
//cout<<"CCC"<<" "<<x<<endl;
if(P(X)==P(PA)){
while(PA!=X) /*cout<<"WWW"<<x<<" "<<X<<" "<<pa<<" "<<PA<<endl,*/ un(X, PA), X=P2(x), PA=P2(e[X].pa);
e[X].pa=-1;
next(X);
}else{
//cout<<x<<" "<<X<<" "<<pa<<" "<<PA<<endl;
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;
if(e[i].d.empty())Ans.pb({i});
}
/*
for (int i=0; i<n; i++){
auto &[s, k, d, pa, v, sz] = e[i];
cout<<i<<":"<<endl;
cout<<"locked: ";for (auto [x, y] : s)cout<<x<<"_"<<y<<" ";cout<<endl;
cout<<"keys: ";for (auto x : k)cout<<x<<" ";cout<<endl;
cout<<"doors: ";while(!d.empty())cout<<d.front()<<" ",d.pop();cout<<endl;
cout<<"pa: ";cout<<pa<<" ";cout<<endl;
cout<<"sz: ";cout<<sz<<" ";cout<<endl;
}return {0};
*/
//cout<<"AAA"<<endl;
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());
//cout<<"OIEJSOJIP"<<an<<endl;
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:146:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | if(an<v.size())continue;
| ~~^~~~~~~~~
keys.cpp: In function 'void next(int, int)':
keys.cpp:102:14: warning: 'PA' may be used uninitialized in this function [-Wmaybe-uninitialized]
102 | unite(X, PA);
| ~~~~~^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
562 ms |
806600 KB |
Output is correct |
2 |
Correct |
549 ms |
806572 KB |
Output is correct |
3 |
Correct |
512 ms |
806468 KB |
Output is correct |
4 |
Correct |
499 ms |
806580 KB |
Output is correct |
5 |
Correct |
483 ms |
806572 KB |
Output is correct |
6 |
Correct |
483 ms |
806572 KB |
Output is correct |
7 |
Correct |
489 ms |
806600 KB |
Output is correct |
8 |
Correct |
494 ms |
806476 KB |
Output is correct |
9 |
Correct |
483 ms |
806580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
562 ms |
806600 KB |
Output is correct |
2 |
Correct |
549 ms |
806572 KB |
Output is correct |
3 |
Correct |
512 ms |
806468 KB |
Output is correct |
4 |
Correct |
499 ms |
806580 KB |
Output is correct |
5 |
Correct |
483 ms |
806572 KB |
Output is correct |
6 |
Correct |
483 ms |
806572 KB |
Output is correct |
7 |
Correct |
489 ms |
806600 KB |
Output is correct |
8 |
Correct |
494 ms |
806476 KB |
Output is correct |
9 |
Correct |
483 ms |
806580 KB |
Output is correct |
10 |
Correct |
479 ms |
806688 KB |
Output is correct |
11 |
Correct |
469 ms |
806636 KB |
Output is correct |
12 |
Correct |
468 ms |
806628 KB |
Output is correct |
13 |
Correct |
485 ms |
806520 KB |
Output is correct |
14 |
Correct |
467 ms |
806472 KB |
Output is correct |
15 |
Correct |
485 ms |
806708 KB |
Output is correct |
16 |
Correct |
481 ms |
806576 KB |
Output is correct |
17 |
Correct |
488 ms |
806576 KB |
Output is correct |
18 |
Correct |
529 ms |
806568 KB |
Output is correct |
19 |
Correct |
486 ms |
806464 KB |
Output is correct |
20 |
Correct |
482 ms |
806696 KB |
Output is correct |
21 |
Correct |
505 ms |
806616 KB |
Output is correct |
22 |
Correct |
492 ms |
806592 KB |
Output is correct |
23 |
Correct |
494 ms |
806680 KB |
Output is correct |
24 |
Correct |
492 ms |
806600 KB |
Output is correct |
25 |
Correct |
499 ms |
806756 KB |
Output is correct |
26 |
Correct |
471 ms |
806580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
562 ms |
806600 KB |
Output is correct |
2 |
Correct |
549 ms |
806572 KB |
Output is correct |
3 |
Correct |
512 ms |
806468 KB |
Output is correct |
4 |
Correct |
499 ms |
806580 KB |
Output is correct |
5 |
Correct |
483 ms |
806572 KB |
Output is correct |
6 |
Correct |
483 ms |
806572 KB |
Output is correct |
7 |
Correct |
489 ms |
806600 KB |
Output is correct |
8 |
Correct |
494 ms |
806476 KB |
Output is correct |
9 |
Correct |
483 ms |
806580 KB |
Output is correct |
10 |
Correct |
479 ms |
806688 KB |
Output is correct |
11 |
Correct |
469 ms |
806636 KB |
Output is correct |
12 |
Correct |
468 ms |
806628 KB |
Output is correct |
13 |
Correct |
485 ms |
806520 KB |
Output is correct |
14 |
Correct |
467 ms |
806472 KB |
Output is correct |
15 |
Correct |
485 ms |
806708 KB |
Output is correct |
16 |
Correct |
481 ms |
806576 KB |
Output is correct |
17 |
Correct |
488 ms |
806576 KB |
Output is correct |
18 |
Correct |
529 ms |
806568 KB |
Output is correct |
19 |
Correct |
486 ms |
806464 KB |
Output is correct |
20 |
Correct |
482 ms |
806696 KB |
Output is correct |
21 |
Correct |
505 ms |
806616 KB |
Output is correct |
22 |
Correct |
492 ms |
806592 KB |
Output is correct |
23 |
Correct |
494 ms |
806680 KB |
Output is correct |
24 |
Correct |
492 ms |
806600 KB |
Output is correct |
25 |
Correct |
499 ms |
806756 KB |
Output is correct |
26 |
Correct |
471 ms |
806580 KB |
Output is correct |
27 |
Correct |
552 ms |
807176 KB |
Output is correct |
28 |
Correct |
492 ms |
807324 KB |
Output is correct |
29 |
Correct |
501 ms |
807336 KB |
Output is correct |
30 |
Correct |
512 ms |
806904 KB |
Output is correct |
31 |
Correct |
474 ms |
806868 KB |
Output is correct |
32 |
Correct |
492 ms |
806664 KB |
Output is correct |
33 |
Correct |
505 ms |
806856 KB |
Output is correct |
34 |
Correct |
566 ms |
806908 KB |
Output is correct |
35 |
Correct |
465 ms |
806740 KB |
Output is correct |
36 |
Correct |
451 ms |
806960 KB |
Output is correct |
37 |
Correct |
509 ms |
807132 KB |
Output is correct |
38 |
Correct |
432 ms |
807320 KB |
Output is correct |
39 |
Correct |
489 ms |
807172 KB |
Output is correct |
40 |
Correct |
465 ms |
806972 KB |
Output is correct |
41 |
Correct |
448 ms |
806960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
562 ms |
806600 KB |
Output is correct |
2 |
Correct |
549 ms |
806572 KB |
Output is correct |
3 |
Correct |
512 ms |
806468 KB |
Output is correct |
4 |
Correct |
499 ms |
806580 KB |
Output is correct |
5 |
Correct |
483 ms |
806572 KB |
Output is correct |
6 |
Correct |
483 ms |
806572 KB |
Output is correct |
7 |
Correct |
489 ms |
806600 KB |
Output is correct |
8 |
Correct |
494 ms |
806476 KB |
Output is correct |
9 |
Correct |
483 ms |
806580 KB |
Output is correct |
10 |
Correct |
868 ms |
871096 KB |
Output is correct |
11 |
Correct |
1223 ms |
896256 KB |
Output is correct |
12 |
Correct |
599 ms |
822360 KB |
Output is correct |
13 |
Correct |
948 ms |
883260 KB |
Output is correct |
14 |
Correct |
884 ms |
869936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
562 ms |
806600 KB |
Output is correct |
2 |
Correct |
549 ms |
806572 KB |
Output is correct |
3 |
Correct |
512 ms |
806468 KB |
Output is correct |
4 |
Correct |
499 ms |
806580 KB |
Output is correct |
5 |
Correct |
483 ms |
806572 KB |
Output is correct |
6 |
Correct |
483 ms |
806572 KB |
Output is correct |
7 |
Correct |
489 ms |
806600 KB |
Output is correct |
8 |
Correct |
494 ms |
806476 KB |
Output is correct |
9 |
Correct |
483 ms |
806580 KB |
Output is correct |
10 |
Correct |
479 ms |
806688 KB |
Output is correct |
11 |
Correct |
469 ms |
806636 KB |
Output is correct |
12 |
Correct |
468 ms |
806628 KB |
Output is correct |
13 |
Correct |
485 ms |
806520 KB |
Output is correct |
14 |
Correct |
467 ms |
806472 KB |
Output is correct |
15 |
Correct |
485 ms |
806708 KB |
Output is correct |
16 |
Correct |
481 ms |
806576 KB |
Output is correct |
17 |
Correct |
488 ms |
806576 KB |
Output is correct |
18 |
Correct |
529 ms |
806568 KB |
Output is correct |
19 |
Correct |
486 ms |
806464 KB |
Output is correct |
20 |
Correct |
482 ms |
806696 KB |
Output is correct |
21 |
Correct |
505 ms |
806616 KB |
Output is correct |
22 |
Correct |
492 ms |
806592 KB |
Output is correct |
23 |
Correct |
494 ms |
806680 KB |
Output is correct |
24 |
Correct |
492 ms |
806600 KB |
Output is correct |
25 |
Correct |
499 ms |
806756 KB |
Output is correct |
26 |
Correct |
471 ms |
806580 KB |
Output is correct |
27 |
Correct |
552 ms |
807176 KB |
Output is correct |
28 |
Correct |
492 ms |
807324 KB |
Output is correct |
29 |
Correct |
501 ms |
807336 KB |
Output is correct |
30 |
Correct |
512 ms |
806904 KB |
Output is correct |
31 |
Correct |
474 ms |
806868 KB |
Output is correct |
32 |
Correct |
492 ms |
806664 KB |
Output is correct |
33 |
Correct |
505 ms |
806856 KB |
Output is correct |
34 |
Correct |
566 ms |
806908 KB |
Output is correct |
35 |
Correct |
465 ms |
806740 KB |
Output is correct |
36 |
Correct |
451 ms |
806960 KB |
Output is correct |
37 |
Correct |
509 ms |
807132 KB |
Output is correct |
38 |
Correct |
432 ms |
807320 KB |
Output is correct |
39 |
Correct |
489 ms |
807172 KB |
Output is correct |
40 |
Correct |
465 ms |
806972 KB |
Output is correct |
41 |
Correct |
448 ms |
806960 KB |
Output is correct |
42 |
Correct |
868 ms |
871096 KB |
Output is correct |
43 |
Correct |
1223 ms |
896256 KB |
Output is correct |
44 |
Correct |
599 ms |
822360 KB |
Output is correct |
45 |
Correct |
948 ms |
883260 KB |
Output is correct |
46 |
Correct |
884 ms |
869936 KB |
Output is correct |
47 |
Correct |
440 ms |
806504 KB |
Output is correct |
48 |
Correct |
475 ms |
806588 KB |
Output is correct |
49 |
Correct |
439 ms |
806516 KB |
Output is correct |
50 |
Correct |
896 ms |
869280 KB |
Output is correct |
51 |
Correct |
840 ms |
872496 KB |
Output is correct |
52 |
Correct |
800 ms |
874348 KB |
Output is correct |
53 |
Correct |
769 ms |
874352 KB |
Output is correct |
54 |
Correct |
744 ms |
874316 KB |
Output is correct |
55 |
Correct |
974 ms |
877640 KB |
Output is correct |
56 |
Correct |
944 ms |
906532 KB |
Output is correct |
57 |
Correct |
1110 ms |
927868 KB |
Output is correct |
58 |
Correct |
994 ms |
883824 KB |
Output is correct |
59 |
Correct |
1316 ms |
889556 KB |
Output is correct |
60 |
Correct |
1220 ms |
889556 KB |
Output is correct |
61 |
Correct |
1155 ms |
891116 KB |
Output is correct |
62 |
Correct |
1453 ms |
952924 KB |
Output is correct |
63 |
Correct |
730 ms |
878184 KB |
Output is correct |
64 |
Correct |
522 ms |
807684 KB |
Output is correct |
65 |
Correct |
498 ms |
807640 KB |
Output is correct |
66 |
Correct |
1437 ms |
952664 KB |
Output is correct |
67 |
Correct |
526 ms |
813236 KB |
Output is correct |
68 |
Correct |
504 ms |
817248 KB |
Output is correct |
69 |
Correct |
1249 ms |
889652 KB |
Output is correct |
70 |
Correct |
578 ms |
828000 KB |
Output is correct |
71 |
Correct |
873 ms |
870236 KB |
Output is correct |
72 |
Correct |
1248 ms |
889600 KB |
Output is correct |
73 |
Correct |
1429 ms |
952764 KB |
Output is correct |