#include "split.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int A , B;
int sub[maxn];
vector<int> canpick;
vector<int> adj[maxn] , adj1[maxn];
int root = -1;
void dfs(int u){
sub[u] = 1;
bool ok = 0;
for(auto & c : adj[u]){
if(sub[c] == -1){
adj1[u].pb(c);
dfs(c);
sub[u] += sub[c];
ok |= sub[c] >= A;
}
}
if(ok == 0 && sub[u] >= A)root = u;
}
void dfs1(int u){
bool ok = 0;
for(auto & c : adj[u]){
if(sub[c] > sub[root])ok = 1;
}
if(u != root && ok){
canpick.pb(u);
return;
}
for(auto & c : adj1[u]){
dfs1(c);
}
}
bool cut[maxn];
bool vis[maxn];
vector<int> valA , valB;
void dfs2(int u){
valA.pb(u);
vis[u] = 1;
for(auto & c : adj1[u]){
if(cut[c])continue;
dfs2(c);
}
}
void dfs3(int u){
valB.pb(u);
vis[u] = 1;
for(auto &c : adj[u]){
if(vis[c] == 1)continue;
dfs3(c);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
for(int i = 0 ; i < p.size() ; ++i){
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
A = min({a , b , c});
memset(sub,-1,sizeof sub);
dfs(0);
dfs1(root);
for(auto & c : canpick){
if(sub[root] - sub[c] < A)break;
sub[root] -= sub[c];
cut[c] = 1;
}
dfs2(root);
for(int i = 0 ; i < n ; ++i){
if(vis[i] == 0){
dfs3(i);
break;
}
}
if(valA.size() > valB.size())swap(valA,valB);
vector<ii> val = {mp(a,1),mp(b,2),mp(c,3)};
sort(val.begin(),val.end());
if(val[0].first <= valA.size() && val[1].first <= valB.size()){
vector<int> res(n , val[2].second);
for(int i = 0 ; i < val[0].first ; ++i){
res[valA[i]] = val[0].second;
}
for(int i = 0 ; i < val[1].first ; ++i){
res[valB[i]] = val[1].second;
}
return res;
}
return vector<int>(n , 0);
}
#ifdef LOCAL
#include "split.h"
#include <cstdio>
#include <cassert>
using namespace std;
int main() {
freopen("A.INP","r",stdin);
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]));
fclose(stdin);
vector<int> result = find_split(n, a, b, c, p, q);
for (int i=0; i<(int)result.size(); i++)
printf("%s%d", ((i>0)?" ":""), result[i]);
printf("\n");
fclose(stdout);
return 0;
}
#endif // LOCAL
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i = 0 ; i < p.size() ; ++i){
| ~~^~~~~~~~~~
split.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if(val[0].first <= valA.size() && val[1].first <= valB.size()){
split.cpp:102:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if(val[0].first <= valA.size() && val[1].first <= valB.size()){
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5376 KB |
ok, correct split |
2 |
Correct |
4 ms |
5376 KB |
ok, correct split |
3 |
Correct |
4 ms |
5376 KB |
ok, correct split |
4 |
Correct |
4 ms |
5376 KB |
ok, correct split |
5 |
Correct |
4 ms |
5376 KB |
ok, correct split |
6 |
Correct |
4 ms |
5376 KB |
ok, correct split |
7 |
Correct |
129 ms |
21848 KB |
ok, correct split |
8 |
Correct |
126 ms |
19440 KB |
ok, correct split |
9 |
Correct |
128 ms |
18672 KB |
ok, correct split |
10 |
Correct |
126 ms |
22128 KB |
ok, correct split |
11 |
Correct |
130 ms |
22128 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5376 KB |
ok, correct split |
2 |
Correct |
4 ms |
5376 KB |
ok, correct split |
3 |
Correct |
4 ms |
5376 KB |
ok, correct split |
4 |
Correct |
152 ms |
17884 KB |
ok, correct split |
5 |
Correct |
112 ms |
12788 KB |
ok, correct split |
6 |
Correct |
128 ms |
22128 KB |
ok, correct split |
7 |
Correct |
127 ms |
19312 KB |
ok, correct split |
8 |
Correct |
167 ms |
15476 KB |
ok, correct split |
9 |
Correct |
133 ms |
14324 KB |
ok, correct split |
10 |
Correct |
65 ms |
11888 KB |
ok, correct split |
11 |
Correct |
64 ms |
11888 KB |
ok, correct split |
12 |
Correct |
63 ms |
11896 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5376 KB |
ok, correct split |
2 |
Correct |
126 ms |
12824 KB |
ok, correct split |
3 |
Correct |
39 ms |
8448 KB |
ok, correct split |
4 |
Correct |
4 ms |
5376 KB |
ok, correct split |
5 |
Correct |
134 ms |
16880 KB |
ok, correct split |
6 |
Correct |
121 ms |
16628 KB |
ok, correct split |
7 |
Correct |
131 ms |
16372 KB |
ok, correct split |
8 |
Correct |
126 ms |
17776 KB |
ok, correct split |
9 |
Correct |
126 ms |
16240 KB |
ok, correct split |
10 |
Correct |
31 ms |
7936 KB |
ok, no valid answer |
11 |
Correct |
49 ms |
9204 KB |
ok, no valid answer |
12 |
Correct |
86 ms |
12400 KB |
ok, no valid answer |
13 |
Correct |
115 ms |
12656 KB |
ok, no valid answer |
14 |
Correct |
67 ms |
11888 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5376 KB |
ok, correct split |
2 |
Correct |
4 ms |
5376 KB |
ok, no valid answer |
3 |
Correct |
4 ms |
5376 KB |
ok, correct split |
4 |
Correct |
4 ms |
5376 KB |
ok, correct split |
5 |
Correct |
5 ms |
5352 KB |
ok, correct split |
6 |
Correct |
4 ms |
5376 KB |
ok, correct split |
7 |
Correct |
4 ms |
5376 KB |
ok, correct split |
8 |
Correct |
4 ms |
5376 KB |
ok, correct split |
9 |
Correct |
7 ms |
5760 KB |
ok, correct split |
10 |
Correct |
6 ms |
5632 KB |
ok, correct split |
11 |
Correct |
4 ms |
5376 KB |
ok, correct split |
12 |
Correct |
6 ms |
5760 KB |
ok, correct split |
13 |
Correct |
4 ms |
5408 KB |
ok, correct split |
14 |
Correct |
4 ms |
5376 KB |
ok, correct split |
15 |
Correct |
4 ms |
5376 KB |
ok, correct split |
16 |
Correct |
4 ms |
5376 KB |
ok, correct split |
17 |
Correct |
4 ms |
5376 KB |
ok, correct split |
18 |
Correct |
4 ms |
5376 KB |
ok, correct split |
19 |
Correct |
4 ms |
5504 KB |
ok, correct split |
20 |
Correct |
5 ms |
5504 KB |
ok, correct split |
21 |
Correct |
6 ms |
5760 KB |
ok, correct split |
22 |
Correct |
5 ms |
5760 KB |
ok, correct split |
23 |
Correct |
6 ms |
5760 KB |
ok, correct split |
24 |
Correct |
6 ms |
5760 KB |
ok, correct split |
25 |
Correct |
6 ms |
5760 KB |
ok, correct split |
26 |
Correct |
6 ms |
5760 KB |
ok, correct split |
27 |
Correct |
6 ms |
5760 KB |
ok, correct split |
28 |
Correct |
6 ms |
5760 KB |
ok, correct split |
29 |
Correct |
4 ms |
5376 KB |
ok, correct split |
30 |
Correct |
6 ms |
5632 KB |
ok, correct split |
31 |
Correct |
4 ms |
5504 KB |
ok, correct split |
32 |
Correct |
4 ms |
5376 KB |
ok, correct split |
33 |
Correct |
4 ms |
5504 KB |
ok, correct split |
34 |
Correct |
6 ms |
5632 KB |
ok, correct split |
35 |
Correct |
6 ms |
5632 KB |
ok, correct split |
36 |
Correct |
5 ms |
5632 KB |
ok, correct split |
37 |
Correct |
6 ms |
5760 KB |
ok, correct split |
38 |
Correct |
6 ms |
5760 KB |
ok, correct split |
39 |
Correct |
6 ms |
5760 KB |
ok, correct split |
40 |
Correct |
6 ms |
5760 KB |
ok, correct split |
41 |
Correct |
5 ms |
5504 KB |
ok, correct split |
42 |
Correct |
5 ms |
5504 KB |
ok, correct split |
43 |
Correct |
6 ms |
5760 KB |
ok, correct split |
44 |
Correct |
8 ms |
5760 KB |
ok, correct split |
45 |
Correct |
7 ms |
5760 KB |
ok, correct split |
46 |
Correct |
6 ms |
5760 KB |
ok, correct split |
47 |
Correct |
6 ms |
5760 KB |
ok, no valid answer |
48 |
Correct |
5 ms |
5632 KB |
ok, correct split |
49 |
Correct |
6 ms |
5760 KB |
ok, correct split |
50 |
Correct |
4 ms |
5376 KB |
ok, no valid answer |
51 |
Correct |
4 ms |
5376 KB |
ok, no valid answer |
52 |
Correct |
5 ms |
5632 KB |
ok, no valid answer |
53 |
Correct |
6 ms |
5760 KB |
ok, no valid answer |
54 |
Correct |
5 ms |
5632 KB |
ok, no valid answer |
55 |
Correct |
6 ms |
5632 KB |
ok, no valid answer |
56 |
Correct |
5 ms |
5632 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5376 KB |
ok, correct split |
2 |
Correct |
4 ms |
5376 KB |
ok, correct split |
3 |
Correct |
4 ms |
5376 KB |
ok, correct split |
4 |
Correct |
4 ms |
5376 KB |
ok, correct split |
5 |
Correct |
4 ms |
5376 KB |
ok, correct split |
6 |
Correct |
4 ms |
5376 KB |
ok, correct split |
7 |
Correct |
129 ms |
21848 KB |
ok, correct split |
8 |
Correct |
126 ms |
19440 KB |
ok, correct split |
9 |
Correct |
128 ms |
18672 KB |
ok, correct split |
10 |
Correct |
126 ms |
22128 KB |
ok, correct split |
11 |
Correct |
130 ms |
22128 KB |
ok, correct split |
12 |
Correct |
4 ms |
5376 KB |
ok, correct split |
13 |
Correct |
4 ms |
5376 KB |
ok, correct split |
14 |
Correct |
4 ms |
5376 KB |
ok, correct split |
15 |
Correct |
152 ms |
17884 KB |
ok, correct split |
16 |
Correct |
112 ms |
12788 KB |
ok, correct split |
17 |
Correct |
128 ms |
22128 KB |
ok, correct split |
18 |
Correct |
127 ms |
19312 KB |
ok, correct split |
19 |
Correct |
167 ms |
15476 KB |
ok, correct split |
20 |
Correct |
133 ms |
14324 KB |
ok, correct split |
21 |
Correct |
65 ms |
11888 KB |
ok, correct split |
22 |
Correct |
64 ms |
11888 KB |
ok, correct split |
23 |
Correct |
63 ms |
11896 KB |
ok, correct split |
24 |
Correct |
4 ms |
5376 KB |
ok, correct split |
25 |
Correct |
126 ms |
12824 KB |
ok, correct split |
26 |
Correct |
39 ms |
8448 KB |
ok, correct split |
27 |
Correct |
4 ms |
5376 KB |
ok, correct split |
28 |
Correct |
134 ms |
16880 KB |
ok, correct split |
29 |
Correct |
121 ms |
16628 KB |
ok, correct split |
30 |
Correct |
131 ms |
16372 KB |
ok, correct split |
31 |
Correct |
126 ms |
17776 KB |
ok, correct split |
32 |
Correct |
126 ms |
16240 KB |
ok, correct split |
33 |
Correct |
31 ms |
7936 KB |
ok, no valid answer |
34 |
Correct |
49 ms |
9204 KB |
ok, no valid answer |
35 |
Correct |
86 ms |
12400 KB |
ok, no valid answer |
36 |
Correct |
115 ms |
12656 KB |
ok, no valid answer |
37 |
Correct |
67 ms |
11888 KB |
ok, no valid answer |
38 |
Correct |
4 ms |
5376 KB |
ok, correct split |
39 |
Correct |
4 ms |
5376 KB |
ok, no valid answer |
40 |
Correct |
4 ms |
5376 KB |
ok, correct split |
41 |
Correct |
4 ms |
5376 KB |
ok, correct split |
42 |
Correct |
5 ms |
5352 KB |
ok, correct split |
43 |
Correct |
4 ms |
5376 KB |
ok, correct split |
44 |
Correct |
4 ms |
5376 KB |
ok, correct split |
45 |
Correct |
4 ms |
5376 KB |
ok, correct split |
46 |
Correct |
7 ms |
5760 KB |
ok, correct split |
47 |
Correct |
6 ms |
5632 KB |
ok, correct split |
48 |
Correct |
4 ms |
5376 KB |
ok, correct split |
49 |
Correct |
6 ms |
5760 KB |
ok, correct split |
50 |
Correct |
4 ms |
5408 KB |
ok, correct split |
51 |
Correct |
4 ms |
5376 KB |
ok, correct split |
52 |
Correct |
4 ms |
5376 KB |
ok, correct split |
53 |
Correct |
4 ms |
5376 KB |
ok, correct split |
54 |
Correct |
4 ms |
5376 KB |
ok, correct split |
55 |
Correct |
4 ms |
5376 KB |
ok, correct split |
56 |
Correct |
4 ms |
5504 KB |
ok, correct split |
57 |
Correct |
5 ms |
5504 KB |
ok, correct split |
58 |
Correct |
6 ms |
5760 KB |
ok, correct split |
59 |
Correct |
5 ms |
5760 KB |
ok, correct split |
60 |
Correct |
6 ms |
5760 KB |
ok, correct split |
61 |
Correct |
6 ms |
5760 KB |
ok, correct split |
62 |
Correct |
6 ms |
5760 KB |
ok, correct split |
63 |
Correct |
6 ms |
5760 KB |
ok, correct split |
64 |
Correct |
6 ms |
5760 KB |
ok, correct split |
65 |
Correct |
6 ms |
5760 KB |
ok, correct split |
66 |
Correct |
4 ms |
5376 KB |
ok, correct split |
67 |
Correct |
6 ms |
5632 KB |
ok, correct split |
68 |
Correct |
4 ms |
5504 KB |
ok, correct split |
69 |
Correct |
4 ms |
5376 KB |
ok, correct split |
70 |
Correct |
4 ms |
5504 KB |
ok, correct split |
71 |
Correct |
6 ms |
5632 KB |
ok, correct split |
72 |
Correct |
6 ms |
5632 KB |
ok, correct split |
73 |
Correct |
5 ms |
5632 KB |
ok, correct split |
74 |
Correct |
6 ms |
5760 KB |
ok, correct split |
75 |
Correct |
6 ms |
5760 KB |
ok, correct split |
76 |
Correct |
6 ms |
5760 KB |
ok, correct split |
77 |
Correct |
6 ms |
5760 KB |
ok, correct split |
78 |
Correct |
5 ms |
5504 KB |
ok, correct split |
79 |
Correct |
5 ms |
5504 KB |
ok, correct split |
80 |
Correct |
6 ms |
5760 KB |
ok, correct split |
81 |
Correct |
8 ms |
5760 KB |
ok, correct split |
82 |
Correct |
7 ms |
5760 KB |
ok, correct split |
83 |
Correct |
6 ms |
5760 KB |
ok, correct split |
84 |
Correct |
6 ms |
5760 KB |
ok, no valid answer |
85 |
Correct |
5 ms |
5632 KB |
ok, correct split |
86 |
Correct |
6 ms |
5760 KB |
ok, correct split |
87 |
Correct |
4 ms |
5376 KB |
ok, no valid answer |
88 |
Correct |
4 ms |
5376 KB |
ok, no valid answer |
89 |
Correct |
5 ms |
5632 KB |
ok, no valid answer |
90 |
Correct |
6 ms |
5760 KB |
ok, no valid answer |
91 |
Correct |
5 ms |
5632 KB |
ok, no valid answer |
92 |
Correct |
6 ms |
5632 KB |
ok, no valid answer |
93 |
Correct |
5 ms |
5632 KB |
ok, no valid answer |
94 |
Correct |
131 ms |
17136 KB |
ok, correct split |
95 |
Correct |
182 ms |
22732 KB |
ok, correct split |
96 |
Correct |
160 ms |
20976 KB |
ok, correct split |
97 |
Correct |
36 ms |
8952 KB |
ok, correct split |
98 |
Correct |
40 ms |
9204 KB |
ok, correct split |
99 |
Correct |
62 ms |
11768 KB |
ok, correct split |
100 |
Correct |
170 ms |
18416 KB |
ok, correct split |
101 |
Correct |
178 ms |
17228 KB |
ok, correct split |
102 |
Correct |
146 ms |
16496 KB |
ok, correct split |
103 |
Correct |
150 ms |
16116 KB |
ok, correct split |
104 |
Correct |
128 ms |
16480 KB |
ok, correct split |
105 |
Correct |
65 ms |
10868 KB |
ok, correct split |
106 |
Correct |
148 ms |
17000 KB |
ok, correct split |
107 |
Correct |
118 ms |
14196 KB |
ok, correct split |
108 |
Correct |
119 ms |
14064 KB |
ok, correct split |
109 |
Correct |
187 ms |
17908 KB |
ok, correct split |
110 |
Correct |
157 ms |
19012 KB |
ok, correct split |
111 |
Correct |
188 ms |
19088 KB |
ok, correct split |
112 |
Correct |
164 ms |
17684 KB |
ok, correct split |
113 |
Correct |
169 ms |
17648 KB |
ok, correct split |
114 |
Correct |
16 ms |
7040 KB |
ok, correct split |
115 |
Correct |
16 ms |
6784 KB |
ok, correct split |
116 |
Correct |
192 ms |
18648 KB |
ok, correct split |
117 |
Correct |
185 ms |
18552 KB |
ok, correct split |
118 |
Correct |
128 ms |
15608 KB |
ok, correct split |
119 |
Correct |
124 ms |
15472 KB |
ok, correct split |
120 |
Correct |
130 ms |
19600 KB |
ok, correct split |
121 |
Correct |
122 ms |
14092 KB |
ok, no valid answer |
122 |
Correct |
104 ms |
13808 KB |
ok, no valid answer |
123 |
Correct |
189 ms |
18468 KB |
ok, no valid answer |
124 |
Correct |
202 ms |
18384 KB |
ok, no valid answer |
125 |
Correct |
110 ms |
14632 KB |
ok, no valid answer |
126 |
Correct |
68 ms |
12256 KB |
ok, no valid answer |
127 |
Correct |
122 ms |
15856 KB |
ok, no valid answer |