#include <bits/stdc++.h>
using namespace std;
const int c=100002;
int n, m, rf[c], si[c], hv[c], ans[c], f[c], pos, cent, t[4], ki, ko, na;
vector<int> sol, sz[c];
bool v[c], v2[c];
void dfs(int a) {
v[a]=true, rf[a]++;
for (int i=0; i<sz[a].size(); i++) {
int x=sz[a][i];
if (!v[x]) f[x]=a, dfs(x), rf[a]+=rf[x];
}
if (!cent && 2*rf[a]>=n) cent=a;
}
int holvan(int a) {
if (!hv[a]) return a;
int x=hv[a];
hv[a]=holvan(x);
return hv[a];
}
void unio(int a, int b) {
a=holvan(a), b=holvan(b);
if (a!=b) {
si[b]+=si[a], si[a]=0, hv[a]=b;
if (si[b]>si[pos]) pos=b;
}
}
void dfs2(int a, int p) {
v2[a]=true;
if (a!=cent) unio(a, p);
for (int i=0; i<sz[a].size(); i++) {
int x=sz[a][i];
if (!v2[x]) {
if (a==cent) dfs2(x, x);
else dfs2(x, p);
}
}
}
void dfs3(int a) {
ans[a]=t[1], ki--;
for (int i=0; i<sz[a].size(); i++) {
int x=sz[a][i];
if (!ans[x] && holvan(x)==pos && ki) dfs3(x);
}
}
void dfs4(int a) {
ans[a]=t[2], ko--;
for (int i=0; i<sz[a].size(); i++) {
int x=sz[a][i];
if (!ans[x] && ko) dfs4(x);
}
}
vector<int> find_split(int cs, int a, int b, int c, vector<int> p, vector<int> q) {
n=cs, m=p.size(), ki=min({a, b, c}), na=max({a, b, c}), ko=n-ki-na;
if (ki==a) t[1]=1;
else if (ki==b) t[1]=2;
else t[1]=3;
if (na==c) t[3]=3;
else if (na==b) t[3]=2;
else t[3]=1;
t[2]=6-t[1]-t[3];
for (int i=0; i<m; i++) {
int x=p[i]+1, y=q[i]+1;
sz[x].push_back(y), sz[y].push_back(x);
}
for (int i=1; i<=n; i++) si[i]=1;
dfs(1), pos=sz[cent][0], dfs2(1, f[cent]);
for (int i=0; i<m; i++) {
int x=p[i]+1, y=q[i]+1;
if (si[pos]<ki && x!=cent && y!=cent) unio(x, y);
}
if (si[pos]>=ki) {
dfs3(pos);
dfs4(cent);
for (int i=1; i<=n; i++) if (!ans[i]) ans[i]=t[3];
}
for (int i=1; i<=n; i++) sol.push_back(ans[i]);
return sol;
}
/*
int b1, b2, b3, b4, b5;
vector<int> b6, b7, b8;
int main()
{
cin >> b1 >> b2 >> b3 >> b4 >> b5;
for (int i=1; i<=b2; i++) {int x; cin >> x; b6.push_back(x);}
for (int i=1; i<=b2; i++) {int x; cin >> x; b7.push_back(x);}
b8=find_split(b1, b3, b4, b5, b6, b7);
for (int i=0; i<b8.size(); i++) cout << b8[i] << " ";
return 0;
}
/*
9 10 3 3 3
0 0 0 0 0 0 1 2 4 5
1 3 4 6 7 8 2 3 5 6
*/
Compilation message
split.cpp:93:1: warning: "/*" within comment [-Wcomment]
/*
split.cpp: In function 'void dfs(int)':
split.cpp:10:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<sz[a].size(); i++) {
~^~~~~~~~~~~~~
split.cpp: In function 'void dfs2(int, int)':
split.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<sz[a].size(); i++) {
~^~~~~~~~~~~~~
split.cpp: In function 'void dfs3(int)':
split.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<sz[a].size(); i++) {
~^~~~~~~~~~~~~
split.cpp: In function 'void dfs4(int)':
split.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<sz[a].size(); i++) {
~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
1 ms |
2688 KB |
ok, correct split |
3 |
Correct |
2 ms |
2688 KB |
ok, correct split |
4 |
Correct |
1 ms |
2688 KB |
ok, correct split |
5 |
Correct |
2 ms |
2688 KB |
ok, correct split |
6 |
Correct |
2 ms |
2688 KB |
ok, correct split |
7 |
Correct |
101 ms |
14836 KB |
ok, correct split |
8 |
Correct |
87 ms |
13556 KB |
ok, correct split |
9 |
Correct |
98 ms |
13044 KB |
ok, correct split |
10 |
Correct |
95 ms |
15092 KB |
ok, correct split |
11 |
Correct |
104 ms |
15092 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
2 ms |
2688 KB |
ok, correct split |
3 |
Correct |
2 ms |
2688 KB |
ok, correct split |
4 |
Correct |
118 ms |
13680 KB |
ok, correct split |
5 |
Correct |
79 ms |
10484 KB |
ok, correct split |
6 |
Correct |
94 ms |
15092 KB |
ok, correct split |
7 |
Correct |
93 ms |
13432 KB |
ok, correct split |
8 |
Correct |
128 ms |
12788 KB |
ok, correct split |
9 |
Correct |
83 ms |
10484 KB |
ok, correct split |
10 |
Correct |
55 ms |
10480 KB |
ok, correct split |
11 |
Correct |
54 ms |
10480 KB |
ok, correct split |
12 |
Correct |
59 ms |
10480 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
105 ms |
10584 KB |
ok, correct split |
3 |
Correct |
29 ms |
6408 KB |
ok, correct split |
4 |
Correct |
3 ms |
2688 KB |
ok, correct split |
5 |
Correct |
111 ms |
12660 KB |
ok, correct split |
6 |
Correct |
101 ms |
12532 KB |
ok, correct split |
7 |
Correct |
97 ms |
12404 KB |
ok, correct split |
8 |
Correct |
98 ms |
13172 KB |
ok, correct split |
9 |
Correct |
93 ms |
12276 KB |
ok, correct split |
10 |
Correct |
25 ms |
5624 KB |
ok, no valid answer |
11 |
Correct |
33 ms |
7036 KB |
ok, no valid answer |
12 |
Correct |
69 ms |
10992 KB |
ok, no valid answer |
13 |
Correct |
71 ms |
10612 KB |
ok, no valid answer |
14 |
Correct |
54 ms |
10480 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
2688 KB |
ok, correct split |
4 |
Correct |
2 ms |
2688 KB |
ok, correct split |
5 |
Correct |
2 ms |
2688 KB |
ok, correct split |
6 |
Correct |
2 ms |
2688 KB |
ok, correct split |
7 |
Correct |
2 ms |
2688 KB |
ok, correct split |
8 |
Correct |
2 ms |
2688 KB |
ok, correct split |
9 |
Correct |
4 ms |
2944 KB |
ok, correct split |
10 |
Correct |
4 ms |
2944 KB |
ok, correct split |
11 |
Correct |
2 ms |
2688 KB |
ok, correct split |
12 |
Correct |
4 ms |
2944 KB |
ok, correct split |
13 |
Correct |
2 ms |
2688 KB |
ok, correct split |
14 |
Correct |
2 ms |
2688 KB |
ok, correct split |
15 |
Correct |
2 ms |
2688 KB |
ok, correct split |
16 |
Correct |
2 ms |
2688 KB |
ok, correct split |
17 |
Correct |
2 ms |
2688 KB |
ok, correct split |
18 |
Correct |
2 ms |
2688 KB |
ok, correct split |
19 |
Correct |
2 ms |
2688 KB |
ok, correct split |
20 |
Correct |
3 ms |
2816 KB |
ok, correct split |
21 |
Correct |
3 ms |
2944 KB |
ok, correct split |
22 |
Correct |
3 ms |
2944 KB |
ok, correct split |
23 |
Correct |
3 ms |
2944 KB |
ok, correct split |
24 |
Correct |
3 ms |
2944 KB |
ok, correct split |
25 |
Correct |
3 ms |
2944 KB |
ok, correct split |
26 |
Correct |
4 ms |
3072 KB |
ok, correct split |
27 |
Correct |
4 ms |
2944 KB |
ok, correct split |
28 |
Correct |
4 ms |
2944 KB |
ok, correct split |
29 |
Correct |
2 ms |
2688 KB |
ok, correct split |
30 |
Correct |
4 ms |
2944 KB |
ok, correct split |
31 |
Correct |
2 ms |
2816 KB |
ok, correct split |
32 |
Correct |
2 ms |
2688 KB |
ok, correct split |
33 |
Correct |
2 ms |
2688 KB |
ok, correct split |
34 |
Correct |
3 ms |
2944 KB |
ok, correct split |
35 |
Correct |
3 ms |
2944 KB |
ok, correct split |
36 |
Correct |
3 ms |
2944 KB |
ok, correct split |
37 |
Correct |
4 ms |
2944 KB |
ok, correct split |
38 |
Correct |
4 ms |
3072 KB |
ok, correct split |
39 |
Correct |
4 ms |
3000 KB |
ok, correct split |
40 |
Correct |
4 ms |
2944 KB |
ok, correct split |
41 |
Correct |
3 ms |
2816 KB |
ok, correct split |
42 |
Correct |
3 ms |
2816 KB |
ok, correct split |
43 |
Correct |
4 ms |
2944 KB |
ok, correct split |
44 |
Correct |
5 ms |
2944 KB |
ok, correct split |
45 |
Correct |
4 ms |
2944 KB |
ok, correct split |
46 |
Correct |
3 ms |
2944 KB |
ok, correct split |
47 |
Correct |
3 ms |
2944 KB |
ok, no valid answer |
48 |
Correct |
5 ms |
2944 KB |
ok, correct split |
49 |
Correct |
5 ms |
2944 KB |
ok, correct split |
50 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
52 |
Correct |
5 ms |
2944 KB |
ok, no valid answer |
53 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
54 |
Correct |
5 ms |
2944 KB |
ok, no valid answer |
55 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
56 |
Correct |
3 ms |
2944 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
ok, correct split |
2 |
Correct |
1 ms |
2688 KB |
ok, correct split |
3 |
Correct |
2 ms |
2688 KB |
ok, correct split |
4 |
Correct |
1 ms |
2688 KB |
ok, correct split |
5 |
Correct |
2 ms |
2688 KB |
ok, correct split |
6 |
Correct |
2 ms |
2688 KB |
ok, correct split |
7 |
Correct |
101 ms |
14836 KB |
ok, correct split |
8 |
Correct |
87 ms |
13556 KB |
ok, correct split |
9 |
Correct |
98 ms |
13044 KB |
ok, correct split |
10 |
Correct |
95 ms |
15092 KB |
ok, correct split |
11 |
Correct |
104 ms |
15092 KB |
ok, correct split |
12 |
Correct |
2 ms |
2688 KB |
ok, correct split |
13 |
Correct |
2 ms |
2688 KB |
ok, correct split |
14 |
Correct |
2 ms |
2688 KB |
ok, correct split |
15 |
Correct |
118 ms |
13680 KB |
ok, correct split |
16 |
Correct |
79 ms |
10484 KB |
ok, correct split |
17 |
Correct |
94 ms |
15092 KB |
ok, correct split |
18 |
Correct |
93 ms |
13432 KB |
ok, correct split |
19 |
Correct |
128 ms |
12788 KB |
ok, correct split |
20 |
Correct |
83 ms |
10484 KB |
ok, correct split |
21 |
Correct |
55 ms |
10480 KB |
ok, correct split |
22 |
Correct |
54 ms |
10480 KB |
ok, correct split |
23 |
Correct |
59 ms |
10480 KB |
ok, correct split |
24 |
Correct |
2 ms |
2688 KB |
ok, correct split |
25 |
Correct |
105 ms |
10584 KB |
ok, correct split |
26 |
Correct |
29 ms |
6408 KB |
ok, correct split |
27 |
Correct |
3 ms |
2688 KB |
ok, correct split |
28 |
Correct |
111 ms |
12660 KB |
ok, correct split |
29 |
Correct |
101 ms |
12532 KB |
ok, correct split |
30 |
Correct |
97 ms |
12404 KB |
ok, correct split |
31 |
Correct |
98 ms |
13172 KB |
ok, correct split |
32 |
Correct |
93 ms |
12276 KB |
ok, correct split |
33 |
Correct |
25 ms |
5624 KB |
ok, no valid answer |
34 |
Correct |
33 ms |
7036 KB |
ok, no valid answer |
35 |
Correct |
69 ms |
10992 KB |
ok, no valid answer |
36 |
Correct |
71 ms |
10612 KB |
ok, no valid answer |
37 |
Correct |
54 ms |
10480 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
2688 KB |
ok, correct split |
39 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
2688 KB |
ok, correct split |
41 |
Correct |
2 ms |
2688 KB |
ok, correct split |
42 |
Correct |
2 ms |
2688 KB |
ok, correct split |
43 |
Correct |
2 ms |
2688 KB |
ok, correct split |
44 |
Correct |
2 ms |
2688 KB |
ok, correct split |
45 |
Correct |
2 ms |
2688 KB |
ok, correct split |
46 |
Correct |
4 ms |
2944 KB |
ok, correct split |
47 |
Correct |
4 ms |
2944 KB |
ok, correct split |
48 |
Correct |
2 ms |
2688 KB |
ok, correct split |
49 |
Correct |
4 ms |
2944 KB |
ok, correct split |
50 |
Correct |
2 ms |
2688 KB |
ok, correct split |
51 |
Correct |
2 ms |
2688 KB |
ok, correct split |
52 |
Correct |
2 ms |
2688 KB |
ok, correct split |
53 |
Correct |
2 ms |
2688 KB |
ok, correct split |
54 |
Correct |
2 ms |
2688 KB |
ok, correct split |
55 |
Correct |
2 ms |
2688 KB |
ok, correct split |
56 |
Correct |
2 ms |
2688 KB |
ok, correct split |
57 |
Correct |
3 ms |
2816 KB |
ok, correct split |
58 |
Correct |
3 ms |
2944 KB |
ok, correct split |
59 |
Correct |
3 ms |
2944 KB |
ok, correct split |
60 |
Correct |
3 ms |
2944 KB |
ok, correct split |
61 |
Correct |
3 ms |
2944 KB |
ok, correct split |
62 |
Correct |
3 ms |
2944 KB |
ok, correct split |
63 |
Correct |
4 ms |
3072 KB |
ok, correct split |
64 |
Correct |
4 ms |
2944 KB |
ok, correct split |
65 |
Correct |
4 ms |
2944 KB |
ok, correct split |
66 |
Correct |
2 ms |
2688 KB |
ok, correct split |
67 |
Correct |
4 ms |
2944 KB |
ok, correct split |
68 |
Correct |
2 ms |
2816 KB |
ok, correct split |
69 |
Correct |
2 ms |
2688 KB |
ok, correct split |
70 |
Correct |
2 ms |
2688 KB |
ok, correct split |
71 |
Correct |
3 ms |
2944 KB |
ok, correct split |
72 |
Correct |
3 ms |
2944 KB |
ok, correct split |
73 |
Correct |
3 ms |
2944 KB |
ok, correct split |
74 |
Correct |
4 ms |
2944 KB |
ok, correct split |
75 |
Correct |
4 ms |
3072 KB |
ok, correct split |
76 |
Correct |
4 ms |
3000 KB |
ok, correct split |
77 |
Correct |
4 ms |
2944 KB |
ok, correct split |
78 |
Correct |
3 ms |
2816 KB |
ok, correct split |
79 |
Correct |
3 ms |
2816 KB |
ok, correct split |
80 |
Correct |
4 ms |
2944 KB |
ok, correct split |
81 |
Correct |
5 ms |
2944 KB |
ok, correct split |
82 |
Correct |
4 ms |
2944 KB |
ok, correct split |
83 |
Correct |
3 ms |
2944 KB |
ok, correct split |
84 |
Correct |
3 ms |
2944 KB |
ok, no valid answer |
85 |
Correct |
5 ms |
2944 KB |
ok, correct split |
86 |
Correct |
5 ms |
2944 KB |
ok, correct split |
87 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
2688 KB |
ok, no valid answer |
89 |
Correct |
5 ms |
2944 KB |
ok, no valid answer |
90 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
91 |
Correct |
5 ms |
2944 KB |
ok, no valid answer |
92 |
Correct |
4 ms |
2944 KB |
ok, no valid answer |
93 |
Correct |
3 ms |
2944 KB |
ok, no valid answer |
94 |
Correct |
119 ms |
13648 KB |
ok, correct split |
95 |
Correct |
166 ms |
18164 KB |
ok, correct split |
96 |
Correct |
147 ms |
16496 KB |
ok, correct split |
97 |
Correct |
28 ms |
6392 KB |
ok, correct split |
98 |
Correct |
31 ms |
6528 KB |
ok, correct split |
99 |
Correct |
52 ms |
8568 KB |
ok, correct split |
100 |
Correct |
135 ms |
15472 KB |
ok, correct split |
101 |
Correct |
113 ms |
14320 KB |
ok, correct split |
102 |
Correct |
119 ms |
13808 KB |
ok, correct split |
103 |
Correct |
108 ms |
13556 KB |
ok, correct split |
104 |
Correct |
114 ms |
15204 KB |
ok, correct split |
105 |
Correct |
51 ms |
8436 KB |
ok, correct split |
106 |
Correct |
98 ms |
15280 KB |
ok, correct split |
107 |
Correct |
77 ms |
11764 KB |
ok, correct split |
108 |
Correct |
78 ms |
11636 KB |
ok, correct split |
109 |
Correct |
133 ms |
14960 KB |
ok, correct split |
110 |
Correct |
148 ms |
14704 KB |
ok, correct split |
111 |
Correct |
139 ms |
14804 KB |
ok, correct split |
112 |
Correct |
128 ms |
14964 KB |
ok, correct split |
113 |
Correct |
124 ms |
14960 KB |
ok, correct split |
114 |
Correct |
13 ms |
4224 KB |
ok, correct split |
115 |
Correct |
12 ms |
4096 KB |
ok, correct split |
116 |
Correct |
132 ms |
14700 KB |
ok, correct split |
117 |
Correct |
119 ms |
14576 KB |
ok, correct split |
118 |
Correct |
81 ms |
11636 KB |
ok, correct split |
119 |
Correct |
96 ms |
11764 KB |
ok, correct split |
120 |
Correct |
94 ms |
14068 KB |
ok, correct split |
121 |
Correct |
79 ms |
11632 KB |
ok, no valid answer |
122 |
Correct |
70 ms |
11376 KB |
ok, no valid answer |
123 |
Correct |
132 ms |
15220 KB |
ok, no valid answer |
124 |
Correct |
131 ms |
15160 KB |
ok, no valid answer |
125 |
Correct |
83 ms |
12400 KB |
ok, no valid answer |
126 |
Correct |
50 ms |
10352 KB |
ok, no valid answer |
127 |
Correct |
96 ms |
12912 KB |
ok, no valid answer |