# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
752656 |
2023-06-03T11:26:43 Z |
Ronin13 |
Keys (IOI21_keys) |
C++17 |
|
1296 ms |
207852 KB |
#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 500001;
int p[nmax][2];
int sz[nmax][2];
void make_set(int v, int ind){
p[v][ind] = v;
sz[v][ind] = 1;
}
int find_set(int v, int ind){
if(p[v][ind] == v){
return v;
}
return p[v][ind] = find_set(p[v][ind], ind);
}
void union_sets(int a, int b, int ind){
a = find_set(a, ind);
b = find_set(b, ind);
if(a == b)
return;
p[b][ind] = a;
sz[a][ind] += sz[b][ind];
}
vector <pii> empt;
struct node{
map <int,int>mp;
set <int> st;
vector <vector <pii> > edg;
int tot = 0;
int sz;
int p;
node(){
}
node(int x){
sz = 1;
p = x;
tot = 0;
edg.pb(empt);
}
void add_edge(int x, int c){
tot++;
if(!mp[c]){
mp[c] = edg.size();
edg.pb(empt);
}
edg[mp[c]].pb({x, c});
}
void add_color(int x){
st.insert(x);
}
int get_edge(int v){
while(!st.empty()){
int x = *st.begin();
int o = mp[x];
if(!o) {st.erase(st.begin());continue;}
while(!edg[o].empty()){
int u = edg[o].back().f;
edg[o].pop_back();
if(find_set(u, 1) != find_set(v, 1)){
return u;
}
}
st.erase(st.begin());
}
return -1;
}
}vert[nmax];
void merg(int u, int v){
u = find_set(u, 1);
v = find_set(v, 1);
if(vert[v].tot > vert[u].tot){
swap(vert[u].edg, vert[v].edg);
swap(vert[u].tot, vert[v].tot);
swap(vert[u].mp, vert[v].mp);
swap(vert[u].st, vert[v].st);
}
for(auto x : vert[v].edg){
for(auto to : x){
vert[u].add_edge(to.f, to.s);
}
}
for(auto x : vert[v].st){
vert[u].st.insert(x);
}
union_sets(u, v, 1);
}
set <int> roots;
int ans = 1e9;
set <int> good;
bool upd(){
if(roots.empty()){
return false;
}
while(!roots.empty()){
int x = *roots.begin();
int val = vert[x].get_edge(x);
if(val == -1){
if(sz[x][1] < ans){
good.clear();
ans = sz[x][1];
good.insert(x);
}
else if(sz[x][1] == ans){
good.insert(x);
}
roots.erase(roots.begin());
}
else{
if(find_set(x, 0) == find_set(val , 0)){
while(find_set(val, 1) != find_set(x, 1)){
int xx = find_set(val, 1);
merg(x, val);
val = vert[xx].p;
}
}
else{
roots.erase(roots.begin());
vert[x].p = val;
union_sets(val, x, 0);
}
return true;
}
}
return false;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size();
for(int i = 0; i < n; i++){
vert[i] = {i};
vert[i].add_color(r[i]);
make_set(i, 0);
make_set(i, 1);
}
for(int i = 0; i < u.size(); i++){
vert[u[i]].add_edge(v[i], c[i]);
vert[v[i]].add_edge(u[i], c[i]);
}
for(int i = 0; i < n; ++i)
roots.insert(i);
while(upd()){}
vector <int> ans(n);
for(int i = 0; i < n; ++i){
if(good.find(find_set(i, 1)) != good.end())
ans[i] = 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:155:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(int i = 0; i < u.size(); i++){
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
66772 KB |
Output is correct |
2 |
Correct |
30 ms |
66772 KB |
Output is correct |
3 |
Correct |
30 ms |
66760 KB |
Output is correct |
4 |
Correct |
31 ms |
66828 KB |
Output is correct |
5 |
Correct |
31 ms |
66772 KB |
Output is correct |
6 |
Correct |
30 ms |
66816 KB |
Output is correct |
7 |
Correct |
31 ms |
66772 KB |
Output is correct |
8 |
Correct |
30 ms |
66780 KB |
Output is correct |
9 |
Correct |
33 ms |
66884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
66772 KB |
Output is correct |
2 |
Correct |
30 ms |
66772 KB |
Output is correct |
3 |
Correct |
30 ms |
66760 KB |
Output is correct |
4 |
Correct |
31 ms |
66828 KB |
Output is correct |
5 |
Correct |
31 ms |
66772 KB |
Output is correct |
6 |
Correct |
30 ms |
66816 KB |
Output is correct |
7 |
Correct |
31 ms |
66772 KB |
Output is correct |
8 |
Correct |
30 ms |
66780 KB |
Output is correct |
9 |
Correct |
33 ms |
66884 KB |
Output is correct |
10 |
Correct |
30 ms |
66876 KB |
Output is correct |
11 |
Correct |
37 ms |
66856 KB |
Output is correct |
12 |
Correct |
31 ms |
66916 KB |
Output is correct |
13 |
Correct |
33 ms |
66804 KB |
Output is correct |
14 |
Correct |
32 ms |
66816 KB |
Output is correct |
15 |
Correct |
32 ms |
66916 KB |
Output is correct |
16 |
Correct |
30 ms |
66768 KB |
Output is correct |
17 |
Correct |
31 ms |
66828 KB |
Output is correct |
18 |
Correct |
31 ms |
66844 KB |
Output is correct |
19 |
Correct |
34 ms |
66832 KB |
Output is correct |
20 |
Correct |
31 ms |
66844 KB |
Output is correct |
21 |
Correct |
31 ms |
66900 KB |
Output is correct |
22 |
Correct |
31 ms |
66832 KB |
Output is correct |
23 |
Correct |
30 ms |
66832 KB |
Output is correct |
24 |
Correct |
29 ms |
66852 KB |
Output is correct |
25 |
Correct |
30 ms |
66840 KB |
Output is correct |
26 |
Correct |
31 ms |
66936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
66772 KB |
Output is correct |
2 |
Correct |
30 ms |
66772 KB |
Output is correct |
3 |
Correct |
30 ms |
66760 KB |
Output is correct |
4 |
Correct |
31 ms |
66828 KB |
Output is correct |
5 |
Correct |
31 ms |
66772 KB |
Output is correct |
6 |
Correct |
30 ms |
66816 KB |
Output is correct |
7 |
Correct |
31 ms |
66772 KB |
Output is correct |
8 |
Correct |
30 ms |
66780 KB |
Output is correct |
9 |
Correct |
33 ms |
66884 KB |
Output is correct |
10 |
Correct |
30 ms |
66876 KB |
Output is correct |
11 |
Correct |
37 ms |
66856 KB |
Output is correct |
12 |
Correct |
31 ms |
66916 KB |
Output is correct |
13 |
Correct |
33 ms |
66804 KB |
Output is correct |
14 |
Correct |
32 ms |
66816 KB |
Output is correct |
15 |
Correct |
32 ms |
66916 KB |
Output is correct |
16 |
Correct |
30 ms |
66768 KB |
Output is correct |
17 |
Correct |
31 ms |
66828 KB |
Output is correct |
18 |
Correct |
31 ms |
66844 KB |
Output is correct |
19 |
Correct |
34 ms |
66832 KB |
Output is correct |
20 |
Correct |
31 ms |
66844 KB |
Output is correct |
21 |
Correct |
31 ms |
66900 KB |
Output is correct |
22 |
Correct |
31 ms |
66832 KB |
Output is correct |
23 |
Correct |
30 ms |
66832 KB |
Output is correct |
24 |
Correct |
29 ms |
66852 KB |
Output is correct |
25 |
Correct |
30 ms |
66840 KB |
Output is correct |
26 |
Correct |
31 ms |
66936 KB |
Output is correct |
27 |
Correct |
33 ms |
67532 KB |
Output is correct |
28 |
Correct |
32 ms |
67476 KB |
Output is correct |
29 |
Correct |
33 ms |
67544 KB |
Output is correct |
30 |
Correct |
34 ms |
67148 KB |
Output is correct |
31 |
Correct |
34 ms |
67104 KB |
Output is correct |
32 |
Correct |
33 ms |
66908 KB |
Output is correct |
33 |
Correct |
33 ms |
67276 KB |
Output is correct |
34 |
Correct |
31 ms |
67180 KB |
Output is correct |
35 |
Correct |
34 ms |
67172 KB |
Output is correct |
36 |
Correct |
37 ms |
67608 KB |
Output is correct |
37 |
Correct |
33 ms |
67752 KB |
Output is correct |
38 |
Correct |
34 ms |
67844 KB |
Output is correct |
39 |
Correct |
42 ms |
67836 KB |
Output is correct |
40 |
Correct |
30 ms |
67312 KB |
Output is correct |
41 |
Correct |
36 ms |
67540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
66772 KB |
Output is correct |
2 |
Correct |
30 ms |
66772 KB |
Output is correct |
3 |
Correct |
30 ms |
66760 KB |
Output is correct |
4 |
Correct |
31 ms |
66828 KB |
Output is correct |
5 |
Correct |
31 ms |
66772 KB |
Output is correct |
6 |
Correct |
30 ms |
66816 KB |
Output is correct |
7 |
Correct |
31 ms |
66772 KB |
Output is correct |
8 |
Correct |
30 ms |
66780 KB |
Output is correct |
9 |
Correct |
33 ms |
66884 KB |
Output is correct |
10 |
Correct |
769 ms |
145412 KB |
Output is correct |
11 |
Correct |
566 ms |
153880 KB |
Output is correct |
12 |
Correct |
170 ms |
91044 KB |
Output is correct |
13 |
Correct |
750 ms |
179456 KB |
Output is correct |
14 |
Correct |
325 ms |
156296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
66772 KB |
Output is correct |
2 |
Correct |
30 ms |
66772 KB |
Output is correct |
3 |
Correct |
30 ms |
66760 KB |
Output is correct |
4 |
Correct |
31 ms |
66828 KB |
Output is correct |
5 |
Correct |
31 ms |
66772 KB |
Output is correct |
6 |
Correct |
30 ms |
66816 KB |
Output is correct |
7 |
Correct |
31 ms |
66772 KB |
Output is correct |
8 |
Correct |
30 ms |
66780 KB |
Output is correct |
9 |
Correct |
33 ms |
66884 KB |
Output is correct |
10 |
Correct |
30 ms |
66876 KB |
Output is correct |
11 |
Correct |
37 ms |
66856 KB |
Output is correct |
12 |
Correct |
31 ms |
66916 KB |
Output is correct |
13 |
Correct |
33 ms |
66804 KB |
Output is correct |
14 |
Correct |
32 ms |
66816 KB |
Output is correct |
15 |
Correct |
32 ms |
66916 KB |
Output is correct |
16 |
Correct |
30 ms |
66768 KB |
Output is correct |
17 |
Correct |
31 ms |
66828 KB |
Output is correct |
18 |
Correct |
31 ms |
66844 KB |
Output is correct |
19 |
Correct |
34 ms |
66832 KB |
Output is correct |
20 |
Correct |
31 ms |
66844 KB |
Output is correct |
21 |
Correct |
31 ms |
66900 KB |
Output is correct |
22 |
Correct |
31 ms |
66832 KB |
Output is correct |
23 |
Correct |
30 ms |
66832 KB |
Output is correct |
24 |
Correct |
29 ms |
66852 KB |
Output is correct |
25 |
Correct |
30 ms |
66840 KB |
Output is correct |
26 |
Correct |
31 ms |
66936 KB |
Output is correct |
27 |
Correct |
33 ms |
67532 KB |
Output is correct |
28 |
Correct |
32 ms |
67476 KB |
Output is correct |
29 |
Correct |
33 ms |
67544 KB |
Output is correct |
30 |
Correct |
34 ms |
67148 KB |
Output is correct |
31 |
Correct |
34 ms |
67104 KB |
Output is correct |
32 |
Correct |
33 ms |
66908 KB |
Output is correct |
33 |
Correct |
33 ms |
67276 KB |
Output is correct |
34 |
Correct |
31 ms |
67180 KB |
Output is correct |
35 |
Correct |
34 ms |
67172 KB |
Output is correct |
36 |
Correct |
37 ms |
67608 KB |
Output is correct |
37 |
Correct |
33 ms |
67752 KB |
Output is correct |
38 |
Correct |
34 ms |
67844 KB |
Output is correct |
39 |
Correct |
42 ms |
67836 KB |
Output is correct |
40 |
Correct |
30 ms |
67312 KB |
Output is correct |
41 |
Correct |
36 ms |
67540 KB |
Output is correct |
42 |
Correct |
769 ms |
145412 KB |
Output is correct |
43 |
Correct |
566 ms |
153880 KB |
Output is correct |
44 |
Correct |
170 ms |
91044 KB |
Output is correct |
45 |
Correct |
750 ms |
179456 KB |
Output is correct |
46 |
Correct |
325 ms |
156296 KB |
Output is correct |
47 |
Correct |
36 ms |
66772 KB |
Output is correct |
48 |
Correct |
35 ms |
66848 KB |
Output is correct |
49 |
Correct |
36 ms |
66824 KB |
Output is correct |
50 |
Correct |
335 ms |
153548 KB |
Output is correct |
51 |
Correct |
354 ms |
152992 KB |
Output is correct |
52 |
Correct |
522 ms |
145228 KB |
Output is correct |
53 |
Correct |
504 ms |
145428 KB |
Output is correct |
54 |
Correct |
512 ms |
145296 KB |
Output is correct |
55 |
Correct |
864 ms |
158256 KB |
Output is correct |
56 |
Correct |
647 ms |
176088 KB |
Output is correct |
57 |
Correct |
555 ms |
162880 KB |
Output is correct |
58 |
Correct |
802 ms |
190040 KB |
Output is correct |
59 |
Correct |
1235 ms |
196268 KB |
Output is correct |
60 |
Correct |
660 ms |
168492 KB |
Output is correct |
61 |
Correct |
1156 ms |
191452 KB |
Output is correct |
62 |
Correct |
1266 ms |
207132 KB |
Output is correct |
63 |
Correct |
386 ms |
167920 KB |
Output is correct |
64 |
Correct |
38 ms |
68420 KB |
Output is correct |
65 |
Correct |
36 ms |
68408 KB |
Output is correct |
66 |
Correct |
1247 ms |
206516 KB |
Output is correct |
67 |
Correct |
67 ms |
76232 KB |
Output is correct |
68 |
Correct |
80 ms |
82440 KB |
Output is correct |
69 |
Correct |
1296 ms |
196240 KB |
Output is correct |
70 |
Correct |
153 ms |
98216 KB |
Output is correct |
71 |
Correct |
365 ms |
161272 KB |
Output is correct |
72 |
Correct |
1267 ms |
196212 KB |
Output is correct |
73 |
Correct |
1277 ms |
207852 KB |
Output is correct |