#include <bits/stdc++.h>
#ifndef LOCAL
#include "split.h"
#endif
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i)
cerr << a[i] << ' ';
cerr << endl;
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
for (auto& x : v)
stream << x << ' ';
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
#ifdef LOCAL
const int maxN = 200;
#else
const int maxN = 1e5 + 5;
#endif
int n;
vector<int> G[maxN], T[maxN], H[maxN];
bool used[maxN];
int comp[maxN], comps, csz[maxN], cfirst[maxN];
bool cused[maxN];
bool forA[maxN];
int dfs1(int v, int& c, int p = -1) {
int sz = 1;
used[v] = 1;
for (int u : G[v]) {
if (used[u] && u != p) continue;
T[v].push_back(u);
if (u == p) continue;
sz += dfs1(u, c, v);
}
if (c == -1 && 2 * sz >= n)
c = v;
return sz;
}
void dfs2(int v, int c, int p = -1) {
comp[v] = c;
if (++csz[c] == 1)
cfirst[c] = v;
for (int u : T[v])
if (u != p)
dfs2(u, c, v);
}
vector<int> find_split(int _n, int A, int B, int C, vector<int> eu, vector<int> ev) {
int m = eu.size();
n = _n;
int sizes[3] = {A, B, C};
int sord[3] = {0, 1, 2};
sort(sord, sord + 3, [&](int i, int j) -> bool {
return sizes[i] < sizes[j];
});
A = sizes[sord[0]], B = sizes[sord[1]];
for (int i = 0; i < m; ++i) {
int u = eu[i], v = ev[i];
G[u].push_back(v);
G[v].push_back(u);
}
int c = -1;
dfs1(0, c);
if (c == -1)
c = 0;
comps = 0;
comp[c] = -1;
for (int v : T[c]) {
dfs2(v, comps++, c);
}
// debug(c);
// mdebug(comp, n);
// for (int v = 0; v < n; ++v)
// for (int u : T[v])
// if (v < u)
// debug(v, u);
// mdebug(csz, comps);
if (*max_element(csz, csz + comps) >= A) {
// cerr << "easy" << endl;
int cl = max_element(csz, csz + comps) - csz;
int v = cfirst[cl];
vector<int> ans(n, 0);
int need;
function<void(int, int, int)> dfs = [&](int v, int c, int p) {
if (need <= 0) return;
--need;
ans[v] = c;
for (int u : T[v])
if (u != p)
dfs(u, c, v);
};
need = A;
dfs(v, sord[0] + 1, c);
need = B;
dfs(c, sord[1] + 1, v);
for (int& x : ans)
if (x == 0)
x = sord[2] + 1;
return ans;
}
for (int i = 0; i < m; ++i) {
int u = eu[i], v = ev[i];
if (u == c || v == c || comp[u] == comp[v]) continue;
H[comp[u]].push_back(comp[v]);
H[comp[v]].push_back(comp[u]);
debug(comp[u], comp[v]);
}
for (int cl = 0; cl < comps; ++cl) {
if (!cused[cl]) {
int sz = 0;
function<void(int)> dfsc = [&](int c) {
cused[c] = 1;
sz += csz[c];
for (int d : H[c])
if (!cused[d])
dfsc(d);
};
dfsc(cl);
if (sz >= A) {
int need = A;
fill(cused, cused + comps, 0);
function<void(int)> dfsc = [&](int c) {
if (need <= 0) return;
need -= csz[c];
cused[c] = 1;
forA[c] = 1;
for (int d : H[c])
if (!cused[d])
dfsc(d);
};
dfsc(cl);
vector<int> ans(n, 0);
function<void(int)> dfsa = [&](int v) {
if (need <= 0) return;
--need;
used[v] = 1;
ans[v] = sord[0] + 1;
for (int u : G[v])
if (!used[u] && u != c && forA[comp[u]])
dfsa(u);
};
need = A;
fill(used, used + n, 0);
dfsa(cfirst[cl]);
function<void(int)> dfsb = [&](int v) {
if (need <= 0) return;
--need;
used[v] = 1;
ans[v] = sord[1] + 1;
for (int u : G[v])
if (!used[u] && !forA[comp[u]])
dfsb(u);
};
need = B;
fill(used, used + n, 0);
dfsb(c);
for (int& x : ans)
if (x == 0)
x = sord[2] + 1;
return ans;
}
}
}
return vector<int>(n, 0);
}
#ifdef LOCAL
int main() {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
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
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:43:24: warning: statement has no effect [-Wunused-value]
43 | #define debug(...) 1337
| ^~~~
split.cpp:157:9: note: in expansion of macro 'debug'
157 | debug(comp[u], comp[v]);
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
ok, correct split |
2 |
Correct |
5 ms |
7244 KB |
ok, correct split |
3 |
Correct |
5 ms |
7244 KB |
ok, correct split |
4 |
Correct |
5 ms |
7244 KB |
ok, correct split |
5 |
Correct |
4 ms |
7372 KB |
ok, correct split |
6 |
Correct |
4 ms |
7372 KB |
ok, correct split |
7 |
Correct |
121 ms |
24904 KB |
ok, correct split |
8 |
Correct |
105 ms |
22284 KB |
ok, correct split |
9 |
Correct |
111 ms |
21456 KB |
ok, correct split |
10 |
Correct |
108 ms |
25420 KB |
ok, correct split |
11 |
Correct |
114 ms |
25416 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
ok, correct split |
2 |
Correct |
5 ms |
7244 KB |
ok, correct split |
3 |
Correct |
5 ms |
7244 KB |
ok, correct split |
4 |
Correct |
128 ms |
21316 KB |
ok, correct split |
5 |
Correct |
98 ms |
16200 KB |
ok, correct split |
6 |
Correct |
106 ms |
25544 KB |
ok, correct split |
7 |
Correct |
114 ms |
21948 KB |
ok, correct split |
8 |
Correct |
139 ms |
18060 KB |
ok, correct split |
9 |
Correct |
115 ms |
16128 KB |
ok, correct split |
10 |
Correct |
75 ms |
17596 KB |
ok, correct split |
11 |
Correct |
72 ms |
17484 KB |
ok, correct split |
12 |
Correct |
71 ms |
17568 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7244 KB |
ok, correct split |
2 |
Correct |
109 ms |
16168 KB |
ok, correct split |
3 |
Correct |
35 ms |
10864 KB |
ok, correct split |
4 |
Correct |
5 ms |
7244 KB |
ok, correct split |
5 |
Correct |
103 ms |
19296 KB |
ok, correct split |
6 |
Correct |
110 ms |
19264 KB |
ok, correct split |
7 |
Correct |
132 ms |
19280 KB |
ok, correct split |
8 |
Correct |
102 ms |
20216 KB |
ok, correct split |
9 |
Correct |
149 ms |
19268 KB |
ok, correct split |
10 |
Correct |
29 ms |
10316 KB |
ok, no valid answer |
11 |
Correct |
42 ms |
11732 KB |
ok, no valid answer |
12 |
Correct |
86 ms |
17144 KB |
ok, no valid answer |
13 |
Correct |
109 ms |
16404 KB |
ok, no valid answer |
14 |
Correct |
74 ms |
17600 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
ok, correct split |
2 |
Correct |
4 ms |
7372 KB |
ok, no valid answer |
3 |
Correct |
4 ms |
7244 KB |
ok, correct split |
4 |
Correct |
5 ms |
7340 KB |
ok, correct split |
5 |
Correct |
7 ms |
7244 KB |
ok, correct split |
6 |
Correct |
6 ms |
7244 KB |
ok, correct split |
7 |
Correct |
6 ms |
7244 KB |
ok, correct split |
8 |
Correct |
5 ms |
7244 KB |
ok, correct split |
9 |
Correct |
7 ms |
7628 KB |
ok, correct split |
10 |
Correct |
8 ms |
7500 KB |
ok, correct split |
11 |
Correct |
5 ms |
7372 KB |
ok, correct split |
12 |
Correct |
7 ms |
7628 KB |
ok, correct split |
13 |
Correct |
5 ms |
7244 KB |
ok, correct split |
14 |
Correct |
6 ms |
7244 KB |
ok, correct split |
15 |
Correct |
5 ms |
7244 KB |
ok, correct split |
16 |
Correct |
5 ms |
7244 KB |
ok, correct split |
17 |
Correct |
5 ms |
7244 KB |
ok, correct split |
18 |
Correct |
5 ms |
7244 KB |
ok, correct split |
19 |
Correct |
6 ms |
7308 KB |
ok, correct split |
20 |
Correct |
6 ms |
7372 KB |
ok, correct split |
21 |
Correct |
6 ms |
7628 KB |
ok, correct split |
22 |
Correct |
7 ms |
7616 KB |
ok, correct split |
23 |
Correct |
7 ms |
7680 KB |
ok, correct split |
24 |
Correct |
6 ms |
7596 KB |
ok, correct split |
25 |
Correct |
6 ms |
7628 KB |
ok, correct split |
26 |
Correct |
7 ms |
7756 KB |
ok, correct split |
27 |
Correct |
7 ms |
7756 KB |
ok, correct split |
28 |
Correct |
7 ms |
7628 KB |
ok, correct split |
29 |
Correct |
5 ms |
7324 KB |
ok, correct split |
30 |
Correct |
6 ms |
7628 KB |
ok, correct split |
31 |
Correct |
5 ms |
7372 KB |
ok, correct split |
32 |
Correct |
4 ms |
7320 KB |
ok, correct split |
33 |
Correct |
5 ms |
7372 KB |
ok, correct split |
34 |
Correct |
7 ms |
7628 KB |
ok, correct split |
35 |
Correct |
7 ms |
7620 KB |
ok, correct split |
36 |
Correct |
7 ms |
7500 KB |
ok, correct split |
37 |
Correct |
7 ms |
7612 KB |
ok, correct split |
38 |
Correct |
8 ms |
7672 KB |
ok, correct split |
39 |
Correct |
7 ms |
7608 KB |
ok, correct split |
40 |
Correct |
6 ms |
7628 KB |
ok, correct split |
41 |
Correct |
6 ms |
7484 KB |
ok, correct split |
42 |
Correct |
5 ms |
7500 KB |
ok, correct split |
43 |
Correct |
7 ms |
7628 KB |
ok, correct split |
44 |
Correct |
7 ms |
7572 KB |
ok, correct split |
45 |
Correct |
7 ms |
7628 KB |
ok, correct split |
46 |
Correct |
6 ms |
7616 KB |
ok, correct split |
47 |
Correct |
6 ms |
7628 KB |
ok, no valid answer |
48 |
Correct |
7 ms |
7484 KB |
ok, correct split |
49 |
Correct |
7 ms |
7628 KB |
ok, correct split |
50 |
Correct |
4 ms |
7372 KB |
ok, no valid answer |
51 |
Correct |
5 ms |
7372 KB |
ok, no valid answer |
52 |
Correct |
6 ms |
7612 KB |
ok, no valid answer |
53 |
Correct |
7 ms |
7620 KB |
ok, no valid answer |
54 |
Correct |
6 ms |
7628 KB |
ok, no valid answer |
55 |
Correct |
7 ms |
7628 KB |
ok, no valid answer |
56 |
Correct |
6 ms |
7628 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7244 KB |
ok, correct split |
2 |
Correct |
5 ms |
7244 KB |
ok, correct split |
3 |
Correct |
5 ms |
7244 KB |
ok, correct split |
4 |
Correct |
5 ms |
7244 KB |
ok, correct split |
5 |
Correct |
4 ms |
7372 KB |
ok, correct split |
6 |
Correct |
4 ms |
7372 KB |
ok, correct split |
7 |
Correct |
121 ms |
24904 KB |
ok, correct split |
8 |
Correct |
105 ms |
22284 KB |
ok, correct split |
9 |
Correct |
111 ms |
21456 KB |
ok, correct split |
10 |
Correct |
108 ms |
25420 KB |
ok, correct split |
11 |
Correct |
114 ms |
25416 KB |
ok, correct split |
12 |
Correct |
4 ms |
7244 KB |
ok, correct split |
13 |
Correct |
5 ms |
7244 KB |
ok, correct split |
14 |
Correct |
5 ms |
7244 KB |
ok, correct split |
15 |
Correct |
128 ms |
21316 KB |
ok, correct split |
16 |
Correct |
98 ms |
16200 KB |
ok, correct split |
17 |
Correct |
106 ms |
25544 KB |
ok, correct split |
18 |
Correct |
114 ms |
21948 KB |
ok, correct split |
19 |
Correct |
139 ms |
18060 KB |
ok, correct split |
20 |
Correct |
115 ms |
16128 KB |
ok, correct split |
21 |
Correct |
75 ms |
17596 KB |
ok, correct split |
22 |
Correct |
72 ms |
17484 KB |
ok, correct split |
23 |
Correct |
71 ms |
17568 KB |
ok, correct split |
24 |
Correct |
5 ms |
7244 KB |
ok, correct split |
25 |
Correct |
109 ms |
16168 KB |
ok, correct split |
26 |
Correct |
35 ms |
10864 KB |
ok, correct split |
27 |
Correct |
5 ms |
7244 KB |
ok, correct split |
28 |
Correct |
103 ms |
19296 KB |
ok, correct split |
29 |
Correct |
110 ms |
19264 KB |
ok, correct split |
30 |
Correct |
132 ms |
19280 KB |
ok, correct split |
31 |
Correct |
102 ms |
20216 KB |
ok, correct split |
32 |
Correct |
149 ms |
19268 KB |
ok, correct split |
33 |
Correct |
29 ms |
10316 KB |
ok, no valid answer |
34 |
Correct |
42 ms |
11732 KB |
ok, no valid answer |
35 |
Correct |
86 ms |
17144 KB |
ok, no valid answer |
36 |
Correct |
109 ms |
16404 KB |
ok, no valid answer |
37 |
Correct |
74 ms |
17600 KB |
ok, no valid answer |
38 |
Correct |
4 ms |
7244 KB |
ok, correct split |
39 |
Correct |
4 ms |
7372 KB |
ok, no valid answer |
40 |
Correct |
4 ms |
7244 KB |
ok, correct split |
41 |
Correct |
5 ms |
7340 KB |
ok, correct split |
42 |
Correct |
7 ms |
7244 KB |
ok, correct split |
43 |
Correct |
6 ms |
7244 KB |
ok, correct split |
44 |
Correct |
6 ms |
7244 KB |
ok, correct split |
45 |
Correct |
5 ms |
7244 KB |
ok, correct split |
46 |
Correct |
7 ms |
7628 KB |
ok, correct split |
47 |
Correct |
8 ms |
7500 KB |
ok, correct split |
48 |
Correct |
5 ms |
7372 KB |
ok, correct split |
49 |
Correct |
7 ms |
7628 KB |
ok, correct split |
50 |
Correct |
5 ms |
7244 KB |
ok, correct split |
51 |
Correct |
6 ms |
7244 KB |
ok, correct split |
52 |
Correct |
5 ms |
7244 KB |
ok, correct split |
53 |
Correct |
5 ms |
7244 KB |
ok, correct split |
54 |
Correct |
5 ms |
7244 KB |
ok, correct split |
55 |
Correct |
5 ms |
7244 KB |
ok, correct split |
56 |
Correct |
6 ms |
7308 KB |
ok, correct split |
57 |
Correct |
6 ms |
7372 KB |
ok, correct split |
58 |
Correct |
6 ms |
7628 KB |
ok, correct split |
59 |
Correct |
7 ms |
7616 KB |
ok, correct split |
60 |
Correct |
7 ms |
7680 KB |
ok, correct split |
61 |
Correct |
6 ms |
7596 KB |
ok, correct split |
62 |
Correct |
6 ms |
7628 KB |
ok, correct split |
63 |
Correct |
7 ms |
7756 KB |
ok, correct split |
64 |
Correct |
7 ms |
7756 KB |
ok, correct split |
65 |
Correct |
7 ms |
7628 KB |
ok, correct split |
66 |
Correct |
5 ms |
7324 KB |
ok, correct split |
67 |
Correct |
6 ms |
7628 KB |
ok, correct split |
68 |
Correct |
5 ms |
7372 KB |
ok, correct split |
69 |
Correct |
4 ms |
7320 KB |
ok, correct split |
70 |
Correct |
5 ms |
7372 KB |
ok, correct split |
71 |
Correct |
7 ms |
7628 KB |
ok, correct split |
72 |
Correct |
7 ms |
7620 KB |
ok, correct split |
73 |
Correct |
7 ms |
7500 KB |
ok, correct split |
74 |
Correct |
7 ms |
7612 KB |
ok, correct split |
75 |
Correct |
8 ms |
7672 KB |
ok, correct split |
76 |
Correct |
7 ms |
7608 KB |
ok, correct split |
77 |
Correct |
6 ms |
7628 KB |
ok, correct split |
78 |
Correct |
6 ms |
7484 KB |
ok, correct split |
79 |
Correct |
5 ms |
7500 KB |
ok, correct split |
80 |
Correct |
7 ms |
7628 KB |
ok, correct split |
81 |
Correct |
7 ms |
7572 KB |
ok, correct split |
82 |
Correct |
7 ms |
7628 KB |
ok, correct split |
83 |
Correct |
6 ms |
7616 KB |
ok, correct split |
84 |
Correct |
6 ms |
7628 KB |
ok, no valid answer |
85 |
Correct |
7 ms |
7484 KB |
ok, correct split |
86 |
Correct |
7 ms |
7628 KB |
ok, correct split |
87 |
Correct |
4 ms |
7372 KB |
ok, no valid answer |
88 |
Correct |
5 ms |
7372 KB |
ok, no valid answer |
89 |
Correct |
6 ms |
7612 KB |
ok, no valid answer |
90 |
Correct |
7 ms |
7620 KB |
ok, no valid answer |
91 |
Correct |
6 ms |
7628 KB |
ok, no valid answer |
92 |
Correct |
7 ms |
7628 KB |
ok, no valid answer |
93 |
Correct |
6 ms |
7628 KB |
ok, no valid answer |
94 |
Correct |
114 ms |
20592 KB |
ok, correct split |
95 |
Correct |
170 ms |
26176 KB |
ok, correct split |
96 |
Correct |
186 ms |
24408 KB |
ok, correct split |
97 |
Correct |
35 ms |
11332 KB |
ok, correct split |
98 |
Correct |
36 ms |
11388 KB |
ok, correct split |
99 |
Correct |
52 ms |
13880 KB |
ok, correct split |
100 |
Correct |
133 ms |
20924 KB |
ok, correct split |
101 |
Correct |
138 ms |
19924 KB |
ok, correct split |
102 |
Correct |
114 ms |
19772 KB |
ok, correct split |
103 |
Correct |
107 ms |
19704 KB |
ok, correct split |
104 |
Correct |
124 ms |
21164 KB |
ok, correct split |
105 |
Correct |
58 ms |
13820 KB |
ok, correct split |
106 |
Correct |
131 ms |
25392 KB |
ok, correct split |
107 |
Correct |
108 ms |
17452 KB |
ok, correct split |
108 |
Correct |
113 ms |
17384 KB |
ok, correct split |
109 |
Correct |
139 ms |
20220 KB |
ok, correct split |
110 |
Correct |
162 ms |
21524 KB |
ok, correct split |
111 |
Correct |
144 ms |
21440 KB |
ok, correct split |
112 |
Correct |
138 ms |
21684 KB |
ok, correct split |
113 |
Correct |
145 ms |
21680 KB |
ok, correct split |
114 |
Correct |
15 ms |
9036 KB |
ok, correct split |
115 |
Correct |
17 ms |
8772 KB |
ok, correct split |
116 |
Correct |
124 ms |
21420 KB |
ok, correct split |
117 |
Correct |
127 ms |
21260 KB |
ok, correct split |
118 |
Correct |
109 ms |
17472 KB |
ok, correct split |
119 |
Correct |
108 ms |
17268 KB |
ok, correct split |
120 |
Correct |
103 ms |
22140 KB |
ok, correct split |
121 |
Correct |
93 ms |
17340 KB |
ok, no valid answer |
122 |
Correct |
91 ms |
17604 KB |
ok, no valid answer |
123 |
Correct |
138 ms |
21180 KB |
ok, no valid answer |
124 |
Correct |
147 ms |
20996 KB |
ok, no valid answer |
125 |
Correct |
99 ms |
19332 KB |
ok, no valid answer |
126 |
Correct |
64 ms |
17724 KB |
ok, no valid answer |
127 |
Correct |
99 ms |
19512 KB |
ok, no valid answer |