#include<bits/stdc++.h>
using namespace std;
#define vec vector<int>
const int N = 1e5+5;
vec G[N];
vec ans;
int colors[] = {1, 2, 3}, sz[N], n, h[N], minh[N], cnt[3];
bool seen[N], colored;
void dfs0(int v)
{
if(cnt[0] == 0 || ans[v] != 0)
return;
//cerr << "dfs0 : " << v << ' ' << colors[0] << endl;
cnt[0]--;
ans[v] = colors[0];
for(int u : G[v])
if(cnt[0] > 0 && h[u] > h[v])
dfs0(u);
}
void dfs1(int v)
{
//cerr << "dfs1 : " << v << ' ' << colors[1] << endl;
cnt[1]--;
ans[v] = colors[1];
for(int u : G[v])
if(cnt[1] > 0 and ans[u] == 0)
dfs1(u);
}
void dfs(int v, int p = N)
{
seen[v] = true;
sz[v] = 1;
h[v] = h[p] + 1;
minh[v] = h[v];
bool t = false;
vec children;
for(int u : G[v])
if(!seen[u])
{
children.push_back(u);
dfs(u, v);
t |= (sz[u] >= cnt[0]);
sz[v] += sz[u];
minh[v] = min(minh[u], minh[v]);
}
else
minh[v] = min(minh[v], h[u]);
if(!t && sz[v] >= cnt[0] && !colored){
// forced size
int fsize = 0;
vec back;
for(int c : children)
if(minh[c] >= h[v])
fsize += sz[c];
else
back.push_back(c);
fsize++; // v itself
while(fsize < cnt[0] && back.size())
{
fsize += sz[back.back()];
back.pop_back();
}
if(fsize >= cnt[1] and n - fsize >= cnt[0])
swap(cnt[1], cnt[0]), swap(colors[0], colors[1]);
if(fsize >= cnt[0] and n - fsize >= cnt[1]){
ans[v] = colors[0];
cnt[0]--;
colored = true;
int p = 0;
for(int u : children)
{
if(p < back.size() and back[p] == u){
p++;
continue;
}
dfs0(u);
}
}
}
}
vec find_split(int n, int a, int b, int c, vec p, vec q)
{
::n = n;
for(int i = 0; i < q.size(); i++)
{
G[q[i]].push_back(p[i]);
G[p[i]].push_back(q[i]);
}
if(a > b)
swap(a, b), swap(colors[0], colors[1]);
if(b > c)
swap(b, c), swap(colors[1], colors[2]);
if(a > b)
swap(a, b), swap(colors[0], colors[1]);
cnt[0] = a, cnt[1] = b, cnt[2] = c;
for(int j = 0; j < 1; j++)
{
ans = vec(n, 0);
dfs(j);
if(colored)
for(int i : ans)
if(i == 0)
{
dfs1(i);
break;
}
if(colored)
for(int &i : ans)
if(i == 0) i = colors[2];
if(colored) break;
}
return ans;
}
/*
int main() {
int n, m, a, b, c;
assert(5 == scanf("%d %d %d %d %d", &n, &m, &a, &b, &c));
vector<int> p(m), q(m);
for (int i=0; i<m; i++)
assert(2 == scanf("%d %d", &p[i], &q[i]));
vector<int> result = find_split(n, a, b, c, p, q);
for (int i=0; i<(int)result.size(); i++)
printf("%d ", result[i]);
printf("\n");
return 0;
}
// */
Compilation message
split.cpp: In function 'void dfs(int, int)':
split.cpp:80:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | if(p < back.size() and back[p] == u){
| ~~^~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < q.size(); i++)
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3676 KB |
ok, correct split |
2 |
Correct |
1 ms |
3676 KB |
ok, correct split |
3 |
Correct |
2 ms |
3676 KB |
ok, correct split |
4 |
Correct |
1 ms |
3676 KB |
ok, correct split |
5 |
Correct |
1 ms |
3676 KB |
ok, correct split |
6 |
Correct |
1 ms |
3676 KB |
ok, correct split |
7 |
Correct |
92 ms |
29780 KB |
ok, correct split |
8 |
Correct |
60 ms |
23636 KB |
ok, correct split |
9 |
Correct |
76 ms |
21584 KB |
ok, correct split |
10 |
Correct |
93 ms |
31020 KB |
ok, correct split |
11 |
Correct |
78 ms |
31068 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3676 KB |
ok, correct split |
2 |
Correct |
1 ms |
3672 KB |
ok, correct split |
3 |
Correct |
1 ms |
3676 KB |
ok, correct split |
4 |
Correct |
74 ms |
20188 KB |
ok, correct split |
5 |
Correct |
49 ms |
9536 KB |
ok, correct split |
6 |
Correct |
74 ms |
31064 KB |
ok, correct split |
7 |
Correct |
70 ms |
23116 KB |
ok, correct split |
8 |
Correct |
82 ms |
11788 KB |
ok, correct split |
9 |
Correct |
50 ms |
9584 KB |
ok, correct split |
10 |
Correct |
36 ms |
10184 KB |
ok, correct split |
11 |
Correct |
39 ms |
10184 KB |
ok, correct split |
12 |
Correct |
42 ms |
10164 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3672 KB |
ok, correct split |
2 |
Correct |
45 ms |
9488 KB |
ok, correct split |
3 |
Correct |
16 ms |
6232 KB |
ok, correct split |
4 |
Correct |
1 ms |
3672 KB |
ok, correct split |
5 |
Correct |
71 ms |
16348 KB |
ok, correct split |
6 |
Correct |
65 ms |
15564 KB |
ok, correct split |
7 |
Correct |
77 ms |
15184 KB |
ok, correct split |
8 |
Correct |
65 ms |
18916 KB |
ok, correct split |
9 |
Correct |
59 ms |
14756 KB |
ok, correct split |
10 |
Correct |
15 ms |
5724 KB |
ok, no valid answer |
11 |
Correct |
23 ms |
6656 KB |
ok, no valid answer |
12 |
Correct |
42 ms |
9924 KB |
ok, no valid answer |
13 |
Correct |
56 ms |
9716 KB |
ok, no valid answer |
14 |
Correct |
43 ms |
10196 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3676 KB |
ok, correct split |
2 |
Correct |
1 ms |
3676 KB |
ok, no valid answer |
3 |
Correct |
1 ms |
3676 KB |
ok, correct split |
4 |
Correct |
1 ms |
3676 KB |
ok, correct split |
5 |
Correct |
1 ms |
3676 KB |
ok, correct split |
6 |
Correct |
1 ms |
3676 KB |
ok, correct split |
7 |
Correct |
1 ms |
3676 KB |
ok, correct split |
8 |
Correct |
2 ms |
3844 KB |
ok, correct split |
9 |
Correct |
3 ms |
4188 KB |
ok, correct split |
10 |
Correct |
3 ms |
3928 KB |
ok, correct split |
11 |
Correct |
2 ms |
3676 KB |
ok, correct split |
12 |
Correct |
3 ms |
3932 KB |
ok, correct split |
13 |
Correct |
1 ms |
3676 KB |
ok, correct split |
14 |
Correct |
2 ms |
3676 KB |
ok, correct split |
15 |
Correct |
2 ms |
3676 KB |
ok, correct split |
16 |
Correct |
2 ms |
3676 KB |
ok, correct split |
17 |
Correct |
1 ms |
3676 KB |
ok, correct split |
18 |
Correct |
1 ms |
3676 KB |
ok, correct split |
19 |
Correct |
1 ms |
3932 KB |
ok, correct split |
20 |
Correct |
2 ms |
3932 KB |
ok, correct split |
21 |
Correct |
2 ms |
4188 KB |
ok, correct split |
22 |
Correct |
2 ms |
3932 KB |
ok, correct split |
23 |
Correct |
2 ms |
4188 KB |
ok, correct split |
24 |
Correct |
3 ms |
4188 KB |
ok, correct split |
25 |
Correct |
3 ms |
4188 KB |
ok, correct split |
26 |
Correct |
2 ms |
3932 KB |
ok, correct split |
27 |
Correct |
2 ms |
3932 KB |
ok, correct split |
28 |
Correct |
2 ms |
3932 KB |
ok, correct split |
29 |
Correct |
1 ms |
3676 KB |
ok, correct split |
30 |
Correct |
3 ms |
3932 KB |
ok, correct split |
31 |
Correct |
2 ms |
3932 KB |
ok, correct split |
32 |
Correct |
1 ms |
3676 KB |
ok, correct split |
33 |
Correct |
1 ms |
3676 KB |
ok, correct split |
34 |
Correct |
2 ms |
3932 KB |
ok, correct split |
35 |
Correct |
2 ms |
3932 KB |
ok, correct split |
36 |
Correct |
2 ms |
3932 KB |
ok, correct split |
37 |
Correct |
3 ms |
3932 KB |
ok, correct split |
38 |
Correct |
3 ms |
3932 KB |
ok, correct split |
39 |
Correct |
3 ms |
3932 KB |
ok, correct split |
40 |
Correct |
3 ms |
3932 KB |
ok, correct split |
41 |
Correct |
2 ms |
3932 KB |
ok, correct split |
42 |
Correct |
2 ms |
3932 KB |
ok, correct split |
43 |
Correct |
3 ms |
3928 KB |
ok, correct split |
44 |
Correct |
3 ms |
3932 KB |
ok, correct split |
45 |
Correct |
3 ms |
3928 KB |
ok, correct split |
46 |
Correct |
2 ms |
4188 KB |
ok, correct split |
47 |
Correct |
3 ms |
4188 KB |
ok, no valid answer |
48 |
Correct |
3 ms |
3884 KB |
ok, correct split |
49 |
Correct |
2 ms |
4340 KB |
ok, correct split |
50 |
Correct |
1 ms |
3676 KB |
ok, no valid answer |
51 |
Correct |
1 ms |
3676 KB |
ok, no valid answer |
52 |
Correct |
2 ms |
3932 KB |
ok, no valid answer |
53 |
Correct |
3 ms |
3932 KB |
ok, no valid answer |
54 |
Correct |
3 ms |
3932 KB |
ok, no valid answer |
55 |
Correct |
3 ms |
3932 KB |
ok, no valid answer |
56 |
Correct |
3 ms |
3932 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
3676 KB |
ok, correct split |
2 |
Correct |
1 ms |
3676 KB |
ok, correct split |
3 |
Correct |
2 ms |
3676 KB |
ok, correct split |
4 |
Correct |
1 ms |
3676 KB |
ok, correct split |
5 |
Correct |
1 ms |
3676 KB |
ok, correct split |
6 |
Correct |
1 ms |
3676 KB |
ok, correct split |
7 |
Correct |
92 ms |
29780 KB |
ok, correct split |
8 |
Correct |
60 ms |
23636 KB |
ok, correct split |
9 |
Correct |
76 ms |
21584 KB |
ok, correct split |
10 |
Correct |
93 ms |
31020 KB |
ok, correct split |
11 |
Correct |
78 ms |
31068 KB |
ok, correct split |
12 |
Correct |
1 ms |
3676 KB |
ok, correct split |
13 |
Correct |
1 ms |
3672 KB |
ok, correct split |
14 |
Correct |
1 ms |
3676 KB |
ok, correct split |
15 |
Correct |
74 ms |
20188 KB |
ok, correct split |
16 |
Correct |
49 ms |
9536 KB |
ok, correct split |
17 |
Correct |
74 ms |
31064 KB |
ok, correct split |
18 |
Correct |
70 ms |
23116 KB |
ok, correct split |
19 |
Correct |
82 ms |
11788 KB |
ok, correct split |
20 |
Correct |
50 ms |
9584 KB |
ok, correct split |
21 |
Correct |
36 ms |
10184 KB |
ok, correct split |
22 |
Correct |
39 ms |
10184 KB |
ok, correct split |
23 |
Correct |
42 ms |
10164 KB |
ok, correct split |
24 |
Correct |
1 ms |
3672 KB |
ok, correct split |
25 |
Correct |
45 ms |
9488 KB |
ok, correct split |
26 |
Correct |
16 ms |
6232 KB |
ok, correct split |
27 |
Correct |
1 ms |
3672 KB |
ok, correct split |
28 |
Correct |
71 ms |
16348 KB |
ok, correct split |
29 |
Correct |
65 ms |
15564 KB |
ok, correct split |
30 |
Correct |
77 ms |
15184 KB |
ok, correct split |
31 |
Correct |
65 ms |
18916 KB |
ok, correct split |
32 |
Correct |
59 ms |
14756 KB |
ok, correct split |
33 |
Correct |
15 ms |
5724 KB |
ok, no valid answer |
34 |
Correct |
23 ms |
6656 KB |
ok, no valid answer |
35 |
Correct |
42 ms |
9924 KB |
ok, no valid answer |
36 |
Correct |
56 ms |
9716 KB |
ok, no valid answer |
37 |
Correct |
43 ms |
10196 KB |
ok, no valid answer |
38 |
Correct |
1 ms |
3676 KB |
ok, correct split |
39 |
Correct |
1 ms |
3676 KB |
ok, no valid answer |
40 |
Correct |
1 ms |
3676 KB |
ok, correct split |
41 |
Correct |
1 ms |
3676 KB |
ok, correct split |
42 |
Correct |
1 ms |
3676 KB |
ok, correct split |
43 |
Correct |
1 ms |
3676 KB |
ok, correct split |
44 |
Correct |
1 ms |
3676 KB |
ok, correct split |
45 |
Correct |
2 ms |
3844 KB |
ok, correct split |
46 |
Correct |
3 ms |
4188 KB |
ok, correct split |
47 |
Correct |
3 ms |
3928 KB |
ok, correct split |
48 |
Correct |
2 ms |
3676 KB |
ok, correct split |
49 |
Correct |
3 ms |
3932 KB |
ok, correct split |
50 |
Correct |
1 ms |
3676 KB |
ok, correct split |
51 |
Correct |
2 ms |
3676 KB |
ok, correct split |
52 |
Correct |
2 ms |
3676 KB |
ok, correct split |
53 |
Correct |
2 ms |
3676 KB |
ok, correct split |
54 |
Correct |
1 ms |
3676 KB |
ok, correct split |
55 |
Correct |
1 ms |
3676 KB |
ok, correct split |
56 |
Correct |
1 ms |
3932 KB |
ok, correct split |
57 |
Correct |
2 ms |
3932 KB |
ok, correct split |
58 |
Correct |
2 ms |
4188 KB |
ok, correct split |
59 |
Correct |
2 ms |
3932 KB |
ok, correct split |
60 |
Correct |
2 ms |
4188 KB |
ok, correct split |
61 |
Correct |
3 ms |
4188 KB |
ok, correct split |
62 |
Correct |
3 ms |
4188 KB |
ok, correct split |
63 |
Correct |
2 ms |
3932 KB |
ok, correct split |
64 |
Correct |
2 ms |
3932 KB |
ok, correct split |
65 |
Correct |
2 ms |
3932 KB |
ok, correct split |
66 |
Correct |
1 ms |
3676 KB |
ok, correct split |
67 |
Correct |
3 ms |
3932 KB |
ok, correct split |
68 |
Correct |
2 ms |
3932 KB |
ok, correct split |
69 |
Correct |
1 ms |
3676 KB |
ok, correct split |
70 |
Correct |
1 ms |
3676 KB |
ok, correct split |
71 |
Correct |
2 ms |
3932 KB |
ok, correct split |
72 |
Correct |
2 ms |
3932 KB |
ok, correct split |
73 |
Correct |
2 ms |
3932 KB |
ok, correct split |
74 |
Correct |
3 ms |
3932 KB |
ok, correct split |
75 |
Correct |
3 ms |
3932 KB |
ok, correct split |
76 |
Correct |
3 ms |
3932 KB |
ok, correct split |
77 |
Correct |
3 ms |
3932 KB |
ok, correct split |
78 |
Correct |
2 ms |
3932 KB |
ok, correct split |
79 |
Correct |
2 ms |
3932 KB |
ok, correct split |
80 |
Correct |
3 ms |
3928 KB |
ok, correct split |
81 |
Correct |
3 ms |
3932 KB |
ok, correct split |
82 |
Correct |
3 ms |
3928 KB |
ok, correct split |
83 |
Correct |
2 ms |
4188 KB |
ok, correct split |
84 |
Correct |
3 ms |
4188 KB |
ok, no valid answer |
85 |
Correct |
3 ms |
3884 KB |
ok, correct split |
86 |
Correct |
2 ms |
4340 KB |
ok, correct split |
87 |
Correct |
1 ms |
3676 KB |
ok, no valid answer |
88 |
Correct |
1 ms |
3676 KB |
ok, no valid answer |
89 |
Correct |
2 ms |
3932 KB |
ok, no valid answer |
90 |
Correct |
3 ms |
3932 KB |
ok, no valid answer |
91 |
Correct |
3 ms |
3932 KB |
ok, no valid answer |
92 |
Correct |
3 ms |
3932 KB |
ok, no valid answer |
93 |
Correct |
3 ms |
3932 KB |
ok, no valid answer |
94 |
Correct |
80 ms |
15700 KB |
ok, correct split |
95 |
Correct |
99 ms |
24660 KB |
ok, correct split |
96 |
Correct |
93 ms |
21880 KB |
ok, correct split |
97 |
Correct |
18 ms |
6236 KB |
ok, correct split |
98 |
Correct |
18 ms |
6236 KB |
ok, correct split |
99 |
Correct |
34 ms |
9820 KB |
ok, correct split |
100 |
Correct |
92 ms |
12628 KB |
ok, correct split |
101 |
Correct |
65 ms |
11976 KB |
ok, correct split |
102 |
Correct |
64 ms |
11236 KB |
ok, correct split |
103 |
Correct |
60 ms |
10920 KB |
ok, correct split |
104 |
Correct |
59 ms |
11964 KB |
ok, correct split |
105 |
Correct |
29 ms |
7624 KB |
ok, correct split |
106 |
Correct |
65 ms |
12484 KB |
ok, correct split |
107 |
Correct |
53 ms |
9504 KB |
ok, correct split |
108 |
Correct |
56 ms |
9508 KB |
ok, correct split |
109 |
Correct |
82 ms |
11752 KB |
ok, correct split |
110 |
Correct |
72 ms |
11408 KB |
ok, correct split |
111 |
Correct |
84 ms |
11716 KB |
ok, correct split |
112 |
Correct |
72 ms |
11776 KB |
ok, correct split |
113 |
Correct |
79 ms |
11776 KB |
ok, correct split |
114 |
Correct |
8 ms |
5468 KB |
ok, correct split |
115 |
Correct |
7 ms |
4968 KB |
ok, correct split |
116 |
Correct |
68 ms |
11464 KB |
ok, correct split |
117 |
Correct |
68 ms |
11464 KB |
ok, correct split |
118 |
Correct |
59 ms |
9756 KB |
ok, correct split |
119 |
Correct |
49 ms |
9536 KB |
ok, correct split |
120 |
Correct |
66 ms |
20560 KB |
ok, correct split |
121 |
Correct |
55 ms |
9392 KB |
ok, no valid answer |
122 |
Correct |
44 ms |
9740 KB |
ok, no valid answer |
123 |
Correct |
75 ms |
13140 KB |
ok, no valid answer |
124 |
Correct |
91 ms |
12880 KB |
ok, no valid answer |
125 |
Correct |
57 ms |
10576 KB |
ok, no valid answer |
126 |
Correct |
33 ms |
9680 KB |
ok, no valid answer |
127 |
Correct |
54 ms |
10748 KB |
ok, no valid answer |