#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int pa[100001], sz[100001], siz[100001], vis[100001], cnt[4];
vector<int> v[100001], ans;
vector<pair<int, int> > v1;
int find(int x){
if(pa[x]==-1) return x;
return pa[x]=find(pa[x]);
}
int uni(int x, int y){
x=find(x); y=find(y);
if(x==y) return 0;
sz[x]+=sz[y]; pa[y]=x;
return sz[x];
}
int getsz(int prev, int now){
int s=1;
for(auto &i:v[now]) if(prev!=i) s+=getsz(now, i);
return siz[now]=s;
}
int getct(int prev, int now, int n){
for(auto &i:v[now]) if(prev!=i && siz[i]>n/2) return getct(now, i, n);
return now;
}
void dfs(int now, int ct, int s, int mx){
vis[now]=1;
if(cnt[s]==mx) return;
cnt[s]++; ans[now]=s;
for(auto &i:v[now]) if(!vis[i] && ct!=i) dfs(i, ct, s, mx);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int x=1, y=2, z=3, m=p.size();
if(a>b) swap(a, b), swap(x, y);
if(b>c) swap(b, c), swap(y, z);
if(a>c) swap(a, c), swap(z, x);
ans.resize(n);
for(int i=0;i<=100000;i++) pa[i]=-1, sz[i]=1;
for(int i=0;i<m;i++){
if(uni(p[i], q[i])) v[p[i]].push_back(q[i]), v[q[i]].push_back(p[i]);
else v1.push_back({p[i], q[i]});
}
getsz(-1, 0);
int ct=getct(-1, 0, n), po=0, pn;
for(auto &i:v[ct]) if(getsz(ct, i)>=a) po=1, pn=i;
if(po){
dfs(pn, ct, x, a); dfs(ct, ct, y, b);
for(auto &i:ans) if(!i) i=z;
return ans;
}
for(int i=0;i<=100000;i++) pa[i]=-1, sz[i]=1;
for(int i=0;i<n;i++) if(i!=ct) for(auto &j:v[i]) if(j!=ct) uni(i, j);
for(auto &[i,j]:v1){
if(i==ct || j==ct) continue;
int s=uni(i, j);
if(s) v[i].push_back(j), v[j].push_back(i);
if(s>=a){
po=1; pn=i; break;
}
}
if(!po) return ans;
dfs(pn, ct, x, a); dfs(ct, ct, y, b);
for(auto &i:ans) if(!i) i=z;
return ans;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:60:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for(auto &[i,j]:v1){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
ok, correct split |
2 |
Correct |
2 ms |
3404 KB |
ok, correct split |
3 |
Correct |
2 ms |
3404 KB |
ok, correct split |
4 |
Correct |
2 ms |
3404 KB |
ok, correct split |
5 |
Correct |
3 ms |
3404 KB |
ok, correct split |
6 |
Correct |
3 ms |
3416 KB |
ok, correct split |
7 |
Correct |
95 ms |
14396 KB |
ok, correct split |
8 |
Correct |
62 ms |
12868 KB |
ok, correct split |
9 |
Correct |
68 ms |
13856 KB |
ok, correct split |
10 |
Correct |
94 ms |
13892 KB |
ok, correct split |
11 |
Correct |
72 ms |
13664 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
ok, correct split |
2 |
Correct |
2 ms |
3416 KB |
ok, correct split |
3 |
Correct |
2 ms |
3420 KB |
ok, correct split |
4 |
Correct |
88 ms |
12244 KB |
ok, correct split |
5 |
Correct |
61 ms |
10932 KB |
ok, correct split |
6 |
Correct |
83 ms |
13904 KB |
ok, correct split |
7 |
Correct |
69 ms |
13892 KB |
ok, correct split |
8 |
Correct |
86 ms |
13960 KB |
ok, correct split |
9 |
Correct |
93 ms |
10828 KB |
ok, correct split |
10 |
Correct |
46 ms |
10824 KB |
ok, correct split |
11 |
Correct |
44 ms |
10832 KB |
ok, correct split |
12 |
Correct |
47 ms |
11180 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
ok, correct split |
2 |
Correct |
66 ms |
10844 KB |
ok, correct split |
3 |
Correct |
24 ms |
6488 KB |
ok, correct split |
4 |
Correct |
2 ms |
3404 KB |
ok, correct split |
5 |
Correct |
86 ms |
12640 KB |
ok, correct split |
6 |
Correct |
78 ms |
12740 KB |
ok, correct split |
7 |
Correct |
71 ms |
12628 KB |
ok, correct split |
8 |
Correct |
108 ms |
12636 KB |
ok, correct split |
9 |
Correct |
81 ms |
12744 KB |
ok, correct split |
10 |
Correct |
20 ms |
5724 KB |
ok, no valid answer |
11 |
Correct |
34 ms |
6980 KB |
ok, no valid answer |
12 |
Correct |
60 ms |
10688 KB |
ok, no valid answer |
13 |
Correct |
63 ms |
10500 KB |
ok, no valid answer |
14 |
Correct |
43 ms |
10848 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3396 KB |
ok, correct split |
2 |
Correct |
2 ms |
3416 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
3416 KB |
ok, correct split |
4 |
Correct |
2 ms |
3432 KB |
ok, correct split |
5 |
Correct |
2 ms |
3404 KB |
ok, correct split |
6 |
Correct |
2 ms |
3416 KB |
ok, correct split |
7 |
Correct |
2 ms |
3404 KB |
ok, correct split |
8 |
Correct |
2 ms |
3404 KB |
ok, correct split |
9 |
Correct |
4 ms |
3544 KB |
ok, correct split |
10 |
Correct |
4 ms |
3660 KB |
ok, correct split |
11 |
Correct |
2 ms |
3412 KB |
ok, correct split |
12 |
Correct |
4 ms |
3660 KB |
ok, correct split |
13 |
Correct |
2 ms |
3404 KB |
ok, correct split |
14 |
Correct |
2 ms |
3404 KB |
ok, correct split |
15 |
Correct |
2 ms |
3404 KB |
ok, correct split |
16 |
Correct |
2 ms |
3404 KB |
ok, correct split |
17 |
Correct |
2 ms |
3404 KB |
ok, correct split |
18 |
Correct |
2 ms |
3424 KB |
ok, correct split |
19 |
Correct |
2 ms |
3404 KB |
ok, correct split |
20 |
Correct |
3 ms |
3404 KB |
ok, correct split |
21 |
Correct |
5 ms |
3660 KB |
ok, correct split |
22 |
Correct |
3 ms |
3660 KB |
ok, correct split |
23 |
Correct |
3 ms |
3660 KB |
ok, correct split |
24 |
Correct |
3 ms |
3604 KB |
ok, correct split |
25 |
Correct |
3 ms |
3556 KB |
ok, correct split |
26 |
Correct |
4 ms |
3660 KB |
ok, correct split |
27 |
Correct |
3 ms |
3660 KB |
ok, correct split |
28 |
Correct |
3 ms |
3624 KB |
ok, correct split |
29 |
Correct |
2 ms |
3404 KB |
ok, correct split |
30 |
Correct |
5 ms |
3688 KB |
ok, correct split |
31 |
Correct |
4 ms |
3404 KB |
ok, correct split |
32 |
Correct |
3 ms |
3404 KB |
ok, correct split |
33 |
Correct |
2 ms |
3424 KB |
ok, correct split |
34 |
Correct |
3 ms |
3532 KB |
ok, correct split |
35 |
Correct |
3 ms |
3532 KB |
ok, correct split |
36 |
Correct |
3 ms |
3552 KB |
ok, correct split |
37 |
Correct |
6 ms |
3660 KB |
ok, correct split |
38 |
Correct |
4 ms |
3632 KB |
ok, correct split |
39 |
Correct |
5 ms |
3660 KB |
ok, correct split |
40 |
Correct |
4 ms |
3684 KB |
ok, correct split |
41 |
Correct |
3 ms |
3532 KB |
ok, correct split |
42 |
Correct |
3 ms |
3560 KB |
ok, correct split |
43 |
Correct |
4 ms |
3684 KB |
ok, correct split |
44 |
Correct |
5 ms |
3688 KB |
ok, correct split |
45 |
Correct |
4 ms |
3692 KB |
ok, correct split |
46 |
Correct |
3 ms |
3592 KB |
ok, correct split |
47 |
Correct |
4 ms |
3532 KB |
ok, no valid answer |
48 |
Correct |
3 ms |
3560 KB |
ok, correct split |
49 |
Correct |
3 ms |
3648 KB |
ok, correct split |
50 |
Correct |
2 ms |
3404 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
3404 KB |
ok, no valid answer |
52 |
Correct |
4 ms |
3532 KB |
ok, no valid answer |
53 |
Correct |
4 ms |
3636 KB |
ok, no valid answer |
54 |
Correct |
3 ms |
3512 KB |
ok, no valid answer |
55 |
Correct |
3 ms |
3660 KB |
ok, no valid answer |
56 |
Correct |
3 ms |
3532 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3404 KB |
ok, correct split |
2 |
Correct |
2 ms |
3404 KB |
ok, correct split |
3 |
Correct |
2 ms |
3404 KB |
ok, correct split |
4 |
Correct |
2 ms |
3404 KB |
ok, correct split |
5 |
Correct |
3 ms |
3404 KB |
ok, correct split |
6 |
Correct |
3 ms |
3416 KB |
ok, correct split |
7 |
Correct |
95 ms |
14396 KB |
ok, correct split |
8 |
Correct |
62 ms |
12868 KB |
ok, correct split |
9 |
Correct |
68 ms |
13856 KB |
ok, correct split |
10 |
Correct |
94 ms |
13892 KB |
ok, correct split |
11 |
Correct |
72 ms |
13664 KB |
ok, correct split |
12 |
Correct |
2 ms |
3404 KB |
ok, correct split |
13 |
Correct |
2 ms |
3416 KB |
ok, correct split |
14 |
Correct |
2 ms |
3420 KB |
ok, correct split |
15 |
Correct |
88 ms |
12244 KB |
ok, correct split |
16 |
Correct |
61 ms |
10932 KB |
ok, correct split |
17 |
Correct |
83 ms |
13904 KB |
ok, correct split |
18 |
Correct |
69 ms |
13892 KB |
ok, correct split |
19 |
Correct |
86 ms |
13960 KB |
ok, correct split |
20 |
Correct |
93 ms |
10828 KB |
ok, correct split |
21 |
Correct |
46 ms |
10824 KB |
ok, correct split |
22 |
Correct |
44 ms |
10832 KB |
ok, correct split |
23 |
Correct |
47 ms |
11180 KB |
ok, correct split |
24 |
Correct |
2 ms |
3404 KB |
ok, correct split |
25 |
Correct |
66 ms |
10844 KB |
ok, correct split |
26 |
Correct |
24 ms |
6488 KB |
ok, correct split |
27 |
Correct |
2 ms |
3404 KB |
ok, correct split |
28 |
Correct |
86 ms |
12640 KB |
ok, correct split |
29 |
Correct |
78 ms |
12740 KB |
ok, correct split |
30 |
Correct |
71 ms |
12628 KB |
ok, correct split |
31 |
Correct |
108 ms |
12636 KB |
ok, correct split |
32 |
Correct |
81 ms |
12744 KB |
ok, correct split |
33 |
Correct |
20 ms |
5724 KB |
ok, no valid answer |
34 |
Correct |
34 ms |
6980 KB |
ok, no valid answer |
35 |
Correct |
60 ms |
10688 KB |
ok, no valid answer |
36 |
Correct |
63 ms |
10500 KB |
ok, no valid answer |
37 |
Correct |
43 ms |
10848 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
3396 KB |
ok, correct split |
39 |
Correct |
2 ms |
3416 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
3416 KB |
ok, correct split |
41 |
Correct |
2 ms |
3432 KB |
ok, correct split |
42 |
Correct |
2 ms |
3404 KB |
ok, correct split |
43 |
Correct |
2 ms |
3416 KB |
ok, correct split |
44 |
Correct |
2 ms |
3404 KB |
ok, correct split |
45 |
Correct |
2 ms |
3404 KB |
ok, correct split |
46 |
Correct |
4 ms |
3544 KB |
ok, correct split |
47 |
Correct |
4 ms |
3660 KB |
ok, correct split |
48 |
Correct |
2 ms |
3412 KB |
ok, correct split |
49 |
Correct |
4 ms |
3660 KB |
ok, correct split |
50 |
Correct |
2 ms |
3404 KB |
ok, correct split |
51 |
Correct |
2 ms |
3404 KB |
ok, correct split |
52 |
Correct |
2 ms |
3404 KB |
ok, correct split |
53 |
Correct |
2 ms |
3404 KB |
ok, correct split |
54 |
Correct |
2 ms |
3404 KB |
ok, correct split |
55 |
Correct |
2 ms |
3424 KB |
ok, correct split |
56 |
Correct |
2 ms |
3404 KB |
ok, correct split |
57 |
Correct |
3 ms |
3404 KB |
ok, correct split |
58 |
Correct |
5 ms |
3660 KB |
ok, correct split |
59 |
Correct |
3 ms |
3660 KB |
ok, correct split |
60 |
Correct |
3 ms |
3660 KB |
ok, correct split |
61 |
Correct |
3 ms |
3604 KB |
ok, correct split |
62 |
Correct |
3 ms |
3556 KB |
ok, correct split |
63 |
Correct |
4 ms |
3660 KB |
ok, correct split |
64 |
Correct |
3 ms |
3660 KB |
ok, correct split |
65 |
Correct |
3 ms |
3624 KB |
ok, correct split |
66 |
Correct |
2 ms |
3404 KB |
ok, correct split |
67 |
Correct |
5 ms |
3688 KB |
ok, correct split |
68 |
Correct |
4 ms |
3404 KB |
ok, correct split |
69 |
Correct |
3 ms |
3404 KB |
ok, correct split |
70 |
Correct |
2 ms |
3424 KB |
ok, correct split |
71 |
Correct |
3 ms |
3532 KB |
ok, correct split |
72 |
Correct |
3 ms |
3532 KB |
ok, correct split |
73 |
Correct |
3 ms |
3552 KB |
ok, correct split |
74 |
Correct |
6 ms |
3660 KB |
ok, correct split |
75 |
Correct |
4 ms |
3632 KB |
ok, correct split |
76 |
Correct |
5 ms |
3660 KB |
ok, correct split |
77 |
Correct |
4 ms |
3684 KB |
ok, correct split |
78 |
Correct |
3 ms |
3532 KB |
ok, correct split |
79 |
Correct |
3 ms |
3560 KB |
ok, correct split |
80 |
Correct |
4 ms |
3684 KB |
ok, correct split |
81 |
Correct |
5 ms |
3688 KB |
ok, correct split |
82 |
Correct |
4 ms |
3692 KB |
ok, correct split |
83 |
Correct |
3 ms |
3592 KB |
ok, correct split |
84 |
Correct |
4 ms |
3532 KB |
ok, no valid answer |
85 |
Correct |
3 ms |
3560 KB |
ok, correct split |
86 |
Correct |
3 ms |
3648 KB |
ok, correct split |
87 |
Correct |
2 ms |
3404 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
3404 KB |
ok, no valid answer |
89 |
Correct |
4 ms |
3532 KB |
ok, no valid answer |
90 |
Correct |
4 ms |
3636 KB |
ok, no valid answer |
91 |
Correct |
3 ms |
3512 KB |
ok, no valid answer |
92 |
Correct |
3 ms |
3660 KB |
ok, no valid answer |
93 |
Correct |
3 ms |
3532 KB |
ok, no valid answer |
94 |
Correct |
86 ms |
11508 KB |
ok, correct split |
95 |
Correct |
93 ms |
14424 KB |
ok, correct split |
96 |
Correct |
90 ms |
13268 KB |
ok, correct split |
97 |
Correct |
22 ms |
6356 KB |
ok, correct split |
98 |
Correct |
28 ms |
6724 KB |
ok, correct split |
99 |
Correct |
34 ms |
8144 KB |
ok, correct split |
100 |
Correct |
90 ms |
14296 KB |
ok, correct split |
101 |
Correct |
77 ms |
13368 KB |
ok, correct split |
102 |
Correct |
81 ms |
13396 KB |
ok, correct split |
103 |
Correct |
72 ms |
13084 KB |
ok, correct split |
104 |
Correct |
78 ms |
14908 KB |
ok, correct split |
105 |
Correct |
38 ms |
8032 KB |
ok, correct split |
106 |
Correct |
73 ms |
14640 KB |
ok, correct split |
107 |
Correct |
64 ms |
10960 KB |
ok, correct split |
108 |
Correct |
63 ms |
10828 KB |
ok, correct split |
109 |
Correct |
100 ms |
14000 KB |
ok, correct split |
110 |
Correct |
96 ms |
14520 KB |
ok, correct split |
111 |
Correct |
136 ms |
14552 KB |
ok, correct split |
112 |
Correct |
89 ms |
14776 KB |
ok, correct split |
113 |
Correct |
103 ms |
14816 KB |
ok, correct split |
114 |
Correct |
13 ms |
4568 KB |
ok, correct split |
115 |
Correct |
9 ms |
4576 KB |
ok, correct split |
116 |
Correct |
76 ms |
14520 KB |
ok, correct split |
117 |
Correct |
89 ms |
14244 KB |
ok, correct split |
118 |
Correct |
65 ms |
10884 KB |
ok, correct split |
119 |
Correct |
65 ms |
10836 KB |
ok, correct split |
120 |
Correct |
71 ms |
12368 KB |
ok, correct split |
121 |
Correct |
88 ms |
10596 KB |
ok, no valid answer |
122 |
Correct |
59 ms |
10596 KB |
ok, no valid answer |
123 |
Correct |
96 ms |
13920 KB |
ok, no valid answer |
124 |
Correct |
120 ms |
13924 KB |
ok, no valid answer |
125 |
Correct |
55 ms |
11740 KB |
ok, no valid answer |
126 |
Correct |
39 ms |
10188 KB |
ok, no valid answer |
127 |
Correct |
68 ms |
12472 KB |
ok, no valid answer |