#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define eb emplace_back
#define SZ(i) int(i.size())
#define X first
#define Y second
#ifdef tmd
#define debug(...) fprintf(stderr,"%d (%s) = ",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do (T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream &printRng (IT bg, IT ed, ostream &os) {
os<<"{";
for (IT it=bg; it!=ed; it++) {
if (it!=bg) {
os<<",";
}
os<<(*it);
}
return os<<"}";
}
template<typename T> ostream &operator << (ostream &os, vector<T> &vec) {
return printRng(vec.begin(), vec.end(), os);
}
#else
#define debug(...)
#endif // tmd
const int MAXN = 100005;
const int MAXM = 200005;
vector<int> edge[MAXN], tree[MAXN], btree[MAXN];
vector<pair<int,int> > gp;
bool vis[MAXN];
int sz[MAXN];
int N;
pair<int,int> msplit = {1, MAXN+1};
void span (int nd) {
vis[nd] = true;
sz[nd] = 1;
for (auto v : edge[nd]) {
if (!vis[v]) {
span(v);
sz[nd] += sz[v];
btree[nd].emplace_back(v);
btree[v].emplace_back(nd);
int cur = min(sz[v], N-sz[v]);
if (cur >= gp[0].first && cur < msplit.second) {
msplit = {v, cur};
}
}
}
}
void dfsSZ (int nd, int par) {
sz[nd] = 1;
for (auto v : btree[nd]) {
if (v != par) {
dfsSZ(v, nd);
sz[nd] += sz[v];
}
}
}
pii dfsCen (int nd, int par) {
int mx = N - sz[nd];
pii bst = {1, N};
for (auto v : btree[nd]) {
if (v != par) {
pii res = dfsCen(v, nd);
if (res.Y < bst.Y) {
bst = res;
}
mx = max(mx, sz[v]);
}
}
if (mx < bst.Y) {
bst = {nd, mx};
}
return bst;
}
int centroid () {
return dfsCen(0,-1).first;
}
vector<int> inv (const vector<int> &s) {
memset(vis, 0, sizeof(vis));
for (const auto v : s) {
vis[v] = true;
}
vector<int> res;
for (int i=0; i<N; i++) {
if (!vis[i]) {
res.emplace_back(i);
}
}
return res;
}
bool inSet[MAXN];
bool vvs[MAXN];
void dfsN (int nd, int par, vector<int> &res, int &cnt, int g) {
vvs[nd] = true;
if (cnt < g) {
cnt++;
res.emplace_back(nd);
for (auto v : edge[nd]) {
if (!vvs[v] && inSet[v]) {
dfsN(v, nd, res, cnt, g);
}
}
}
}
vector<int> trim (const vector<int> &s, int g) {
memset(inSet, 0, sizeof(inSet));
for (auto v : s) {
inSet[v] = true;
}
vector<int> ret;
int cnt = 0;
dfsN(s.front(), -1, ret, cnt, g);
return ret;
}
struct Subtree {
int sz;
vector<int> element;
Subtree () {
sz = 0;
}
};
vector<Subtree> child;
void dfsSub (int nd, int par, Subtree &cur) {
cur.sz++;
cur.element.eb(nd);
for (auto v : btree[nd]) {
if (par != v) {
dfsSub(v, nd, cur);
}
}
}
int id[MAXN];
vector<int> sedg[MAXN];
int A;
bool vs[MAXN];
void dfsAns (int nd, vector<int> &res, int &wsum) {
if (wsum >= A) {
return;
}
vs[nd] = true;
res.eb(nd);
wsum += child[nd].sz;
for (auto v : sedg[nd]) {
if (!vs[v]) {
dfsAns(v, res, wsum);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n;
gp = {{a,1}, {b,2}, {c,3}};
sort(gp.begin(), gp.end());
A = gp[0].first;
int m = p.size();
for (int i=0; i<m; i++) {
int u = p[i];
int v = q[i];
edge[u].emplace_back(v);
edge[v].emplace_back(u);
}
span(0);
int cen = centroid();
debug(cen);
int mx = 0;
for (auto v : btree[cen]) {
Subtree cur;
dfsSub(v, cen, cur);
for (auto el : cur.element) {
id[el] = child.size();
}
debug(v, cur.element);
if (cur.sz >= gp[0].first) {
mx = child.size();
}
child.eb(cur);
}
vector<int> aset, bset;
if (child[mx].sz >= gp[0].first) {
aset = child[mx].element;
bset = inv(aset);
if (aset.size() > bset.size()) {
swap(aset, bset);
}
assert(aset.size() >= gp[0].first);
assert(bset.size() >= gp[1].first);
} else {
int cc = SZ(child);
for (int i=0; i<m; i++) {
int u = p[i];
int v = q[i];
if (u == cen || v == cen) {
continue;
}
if (id[u] != id[v]) {
sedg[id[u]].eb(id[v]);
sedg[id[v]].eb(id[u]);
}
}
bool fnd = false;
for (int i=0; i<cc; i++) {
if (!vs[i]) {
vector<int> vec;
int wsum = 0;
dfsAns(i, vec, wsum);
debug(vec, wsum);
if (wsum >= gp[0].first) {
for (auto v : vec) {
for (auto nd : child[v].element) {
aset.eb(nd);
}
}
bset = inv(aset);
fnd = true;
break;
}
}
}
if (!fnd) {
return vector<int>(n,0);
}
}
if (aset.size() > bset.size()) {
swap(aset, bset);
}
assert(aset.size() >= gp[0].first);
assert(bset.size() >= gp[1].first);
aset = trim(aset,gp[0].first);
bset = trim(bset,gp[1].first);
// assert(aset.size() == gp[0].first);
// assert(bset.size() == gp[1].first);
vector<int> ret(n, gp[2].second);
for (auto v : aset) {
ret[v] = gp[0].second;
}
for (auto v : bset) {
ret[v] = gp[1].second;
}
return ret;
}
Compilation message
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from split.cpp:2:
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:221:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(aset.size() >= gp[0].first);
~~~~~~~~~~~~^~~~~~~~~~
split.cpp:222:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(bset.size() >= gp[1].first);
~~~~~~~~~~~~^~~~~~~~~~
split.cpp:268:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(aset.size() >= gp[0].first);
~~~~~~~~~~~~^~~~~~~~~~
split.cpp:269:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(bset.size() >= gp[1].first);
~~~~~~~~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
ok, correct split |
2 |
Correct |
10 ms |
9848 KB |
ok, correct split |
3 |
Correct |
11 ms |
9976 KB |
ok, correct split |
4 |
Correct |
10 ms |
9852 KB |
ok, correct split |
5 |
Correct |
10 ms |
9976 KB |
ok, correct split |
6 |
Correct |
11 ms |
9976 KB |
ok, correct split |
7 |
Correct |
137 ms |
27440 KB |
ok, correct split |
8 |
Correct |
120 ms |
24752 KB |
ok, correct split |
9 |
Correct |
131 ms |
24368 KB |
ok, correct split |
10 |
Correct |
121 ms |
27440 KB |
ok, correct split |
11 |
Correct |
135 ms |
27824 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
ok, correct split |
2 |
Correct |
10 ms |
9848 KB |
ok, correct split |
3 |
Correct |
10 ms |
9848 KB |
ok, correct split |
4 |
Correct |
151 ms |
24328 KB |
ok, correct split |
5 |
Correct |
122 ms |
20068 KB |
ok, correct split |
6 |
Correct |
124 ms |
27440 KB |
ok, correct split |
7 |
Correct |
131 ms |
24880 KB |
ok, correct split |
8 |
Correct |
172 ms |
21872 KB |
ok, correct split |
9 |
Correct |
124 ms |
19856 KB |
ok, correct split |
10 |
Correct |
105 ms |
26592 KB |
ok, correct split |
11 |
Correct |
98 ms |
26592 KB |
ok, correct split |
12 |
Correct |
99 ms |
26592 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
ok, correct split |
2 |
Correct |
126 ms |
20324 KB |
ok, correct split |
3 |
Correct |
44 ms |
13952 KB |
ok, correct split |
4 |
Correct |
10 ms |
9848 KB |
ok, correct split |
5 |
Correct |
129 ms |
22664 KB |
ok, correct split |
6 |
Correct |
132 ms |
22352 KB |
ok, correct split |
7 |
Correct |
126 ms |
22272 KB |
ok, correct split |
8 |
Correct |
127 ms |
23556 KB |
ok, correct split |
9 |
Correct |
130 ms |
22024 KB |
ok, correct split |
10 |
Correct |
37 ms |
13048 KB |
ok, no valid answer |
11 |
Correct |
52 ms |
14712 KB |
ok, no valid answer |
12 |
Correct |
105 ms |
23400 KB |
ok, no valid answer |
13 |
Correct |
115 ms |
20208 KB |
ok, no valid answer |
14 |
Correct |
101 ms |
25952 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9848 KB |
ok, correct split |
2 |
Correct |
11 ms |
9720 KB |
ok, no valid answer |
3 |
Correct |
10 ms |
9848 KB |
ok, correct split |
4 |
Correct |
10 ms |
9848 KB |
ok, correct split |
5 |
Correct |
11 ms |
9976 KB |
ok, correct split |
6 |
Correct |
10 ms |
9848 KB |
ok, correct split |
7 |
Correct |
11 ms |
9848 KB |
ok, correct split |
8 |
Correct |
10 ms |
9848 KB |
ok, correct split |
9 |
Correct |
13 ms |
10232 KB |
ok, correct split |
10 |
Correct |
13 ms |
10232 KB |
ok, correct split |
11 |
Correct |
11 ms |
9976 KB |
ok, correct split |
12 |
Correct |
12 ms |
10232 KB |
ok, correct split |
13 |
Correct |
10 ms |
9848 KB |
ok, correct split |
14 |
Correct |
10 ms |
9848 KB |
ok, correct split |
15 |
Correct |
11 ms |
9976 KB |
ok, correct split |
16 |
Correct |
11 ms |
10024 KB |
ok, correct split |
17 |
Correct |
10 ms |
9976 KB |
ok, correct split |
18 |
Correct |
10 ms |
9980 KB |
ok, correct split |
19 |
Correct |
11 ms |
9976 KB |
ok, correct split |
20 |
Correct |
10 ms |
9976 KB |
ok, correct split |
21 |
Correct |
12 ms |
10232 KB |
ok, correct split |
22 |
Correct |
18 ms |
10232 KB |
ok, correct split |
23 |
Correct |
12 ms |
10232 KB |
ok, correct split |
24 |
Correct |
12 ms |
10232 KB |
ok, correct split |
25 |
Correct |
12 ms |
10232 KB |
ok, correct split |
26 |
Correct |
13 ms |
10488 KB |
ok, correct split |
27 |
Correct |
14 ms |
10616 KB |
ok, correct split |
28 |
Correct |
15 ms |
10488 KB |
ok, correct split |
29 |
Correct |
10 ms |
9976 KB |
ok, correct split |
30 |
Correct |
13 ms |
10360 KB |
ok, correct split |
31 |
Correct |
11 ms |
9976 KB |
ok, correct split |
32 |
Correct |
11 ms |
9976 KB |
ok, correct split |
33 |
Correct |
11 ms |
9976 KB |
ok, correct split |
34 |
Correct |
15 ms |
10360 KB |
ok, correct split |
35 |
Correct |
12 ms |
10232 KB |
ok, correct split |
36 |
Correct |
12 ms |
10232 KB |
ok, correct split |
37 |
Correct |
13 ms |
10360 KB |
ok, correct split |
38 |
Correct |
13 ms |
10360 KB |
ok, correct split |
39 |
Correct |
13 ms |
10360 KB |
ok, correct split |
40 |
Correct |
13 ms |
10232 KB |
ok, correct split |
41 |
Correct |
12 ms |
10104 KB |
ok, correct split |
42 |
Correct |
12 ms |
10104 KB |
ok, correct split |
43 |
Correct |
15 ms |
10616 KB |
ok, correct split |
44 |
Correct |
13 ms |
10360 KB |
ok, correct split |
45 |
Correct |
13 ms |
10360 KB |
ok, correct split |
46 |
Correct |
12 ms |
10364 KB |
ok, correct split |
47 |
Correct |
12 ms |
10104 KB |
ok, no valid answer |
48 |
Correct |
12 ms |
10236 KB |
ok, correct split |
49 |
Correct |
12 ms |
10360 KB |
ok, correct split |
50 |
Correct |
10 ms |
9720 KB |
ok, no valid answer |
51 |
Correct |
10 ms |
9720 KB |
ok, no valid answer |
52 |
Correct |
12 ms |
9976 KB |
ok, no valid answer |
53 |
Correct |
13 ms |
10104 KB |
ok, no valid answer |
54 |
Correct |
12 ms |
10232 KB |
ok, no valid answer |
55 |
Correct |
12 ms |
10104 KB |
ok, no valid answer |
56 |
Correct |
13 ms |
10104 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
ok, correct split |
2 |
Correct |
10 ms |
9848 KB |
ok, correct split |
3 |
Correct |
11 ms |
9976 KB |
ok, correct split |
4 |
Correct |
10 ms |
9852 KB |
ok, correct split |
5 |
Correct |
10 ms |
9976 KB |
ok, correct split |
6 |
Correct |
11 ms |
9976 KB |
ok, correct split |
7 |
Correct |
137 ms |
27440 KB |
ok, correct split |
8 |
Correct |
120 ms |
24752 KB |
ok, correct split |
9 |
Correct |
131 ms |
24368 KB |
ok, correct split |
10 |
Correct |
121 ms |
27440 KB |
ok, correct split |
11 |
Correct |
135 ms |
27824 KB |
ok, correct split |
12 |
Correct |
10 ms |
9848 KB |
ok, correct split |
13 |
Correct |
10 ms |
9848 KB |
ok, correct split |
14 |
Correct |
10 ms |
9848 KB |
ok, correct split |
15 |
Correct |
151 ms |
24328 KB |
ok, correct split |
16 |
Correct |
122 ms |
20068 KB |
ok, correct split |
17 |
Correct |
124 ms |
27440 KB |
ok, correct split |
18 |
Correct |
131 ms |
24880 KB |
ok, correct split |
19 |
Correct |
172 ms |
21872 KB |
ok, correct split |
20 |
Correct |
124 ms |
19856 KB |
ok, correct split |
21 |
Correct |
105 ms |
26592 KB |
ok, correct split |
22 |
Correct |
98 ms |
26592 KB |
ok, correct split |
23 |
Correct |
99 ms |
26592 KB |
ok, correct split |
24 |
Correct |
10 ms |
9848 KB |
ok, correct split |
25 |
Correct |
126 ms |
20324 KB |
ok, correct split |
26 |
Correct |
44 ms |
13952 KB |
ok, correct split |
27 |
Correct |
10 ms |
9848 KB |
ok, correct split |
28 |
Correct |
129 ms |
22664 KB |
ok, correct split |
29 |
Correct |
132 ms |
22352 KB |
ok, correct split |
30 |
Correct |
126 ms |
22272 KB |
ok, correct split |
31 |
Correct |
127 ms |
23556 KB |
ok, correct split |
32 |
Correct |
130 ms |
22024 KB |
ok, correct split |
33 |
Correct |
37 ms |
13048 KB |
ok, no valid answer |
34 |
Correct |
52 ms |
14712 KB |
ok, no valid answer |
35 |
Correct |
105 ms |
23400 KB |
ok, no valid answer |
36 |
Correct |
115 ms |
20208 KB |
ok, no valid answer |
37 |
Correct |
101 ms |
25952 KB |
ok, no valid answer |
38 |
Correct |
11 ms |
9848 KB |
ok, correct split |
39 |
Correct |
11 ms |
9720 KB |
ok, no valid answer |
40 |
Correct |
10 ms |
9848 KB |
ok, correct split |
41 |
Correct |
10 ms |
9848 KB |
ok, correct split |
42 |
Correct |
11 ms |
9976 KB |
ok, correct split |
43 |
Correct |
10 ms |
9848 KB |
ok, correct split |
44 |
Correct |
11 ms |
9848 KB |
ok, correct split |
45 |
Correct |
10 ms |
9848 KB |
ok, correct split |
46 |
Correct |
13 ms |
10232 KB |
ok, correct split |
47 |
Correct |
13 ms |
10232 KB |
ok, correct split |
48 |
Correct |
11 ms |
9976 KB |
ok, correct split |
49 |
Correct |
12 ms |
10232 KB |
ok, correct split |
50 |
Correct |
10 ms |
9848 KB |
ok, correct split |
51 |
Correct |
10 ms |
9848 KB |
ok, correct split |
52 |
Correct |
11 ms |
9976 KB |
ok, correct split |
53 |
Correct |
11 ms |
10024 KB |
ok, correct split |
54 |
Correct |
10 ms |
9976 KB |
ok, correct split |
55 |
Correct |
10 ms |
9980 KB |
ok, correct split |
56 |
Correct |
11 ms |
9976 KB |
ok, correct split |
57 |
Correct |
10 ms |
9976 KB |
ok, correct split |
58 |
Correct |
12 ms |
10232 KB |
ok, correct split |
59 |
Correct |
18 ms |
10232 KB |
ok, correct split |
60 |
Correct |
12 ms |
10232 KB |
ok, correct split |
61 |
Correct |
12 ms |
10232 KB |
ok, correct split |
62 |
Correct |
12 ms |
10232 KB |
ok, correct split |
63 |
Correct |
13 ms |
10488 KB |
ok, correct split |
64 |
Correct |
14 ms |
10616 KB |
ok, correct split |
65 |
Correct |
15 ms |
10488 KB |
ok, correct split |
66 |
Correct |
10 ms |
9976 KB |
ok, correct split |
67 |
Correct |
13 ms |
10360 KB |
ok, correct split |
68 |
Correct |
11 ms |
9976 KB |
ok, correct split |
69 |
Correct |
11 ms |
9976 KB |
ok, correct split |
70 |
Correct |
11 ms |
9976 KB |
ok, correct split |
71 |
Correct |
15 ms |
10360 KB |
ok, correct split |
72 |
Correct |
12 ms |
10232 KB |
ok, correct split |
73 |
Correct |
12 ms |
10232 KB |
ok, correct split |
74 |
Correct |
13 ms |
10360 KB |
ok, correct split |
75 |
Correct |
13 ms |
10360 KB |
ok, correct split |
76 |
Correct |
13 ms |
10360 KB |
ok, correct split |
77 |
Correct |
13 ms |
10232 KB |
ok, correct split |
78 |
Correct |
12 ms |
10104 KB |
ok, correct split |
79 |
Correct |
12 ms |
10104 KB |
ok, correct split |
80 |
Correct |
15 ms |
10616 KB |
ok, correct split |
81 |
Correct |
13 ms |
10360 KB |
ok, correct split |
82 |
Correct |
13 ms |
10360 KB |
ok, correct split |
83 |
Correct |
12 ms |
10364 KB |
ok, correct split |
84 |
Correct |
12 ms |
10104 KB |
ok, no valid answer |
85 |
Correct |
12 ms |
10236 KB |
ok, correct split |
86 |
Correct |
12 ms |
10360 KB |
ok, correct split |
87 |
Correct |
10 ms |
9720 KB |
ok, no valid answer |
88 |
Correct |
10 ms |
9720 KB |
ok, no valid answer |
89 |
Correct |
12 ms |
9976 KB |
ok, no valid answer |
90 |
Correct |
13 ms |
10104 KB |
ok, no valid answer |
91 |
Correct |
12 ms |
10232 KB |
ok, no valid answer |
92 |
Correct |
12 ms |
10104 KB |
ok, no valid answer |
93 |
Correct |
13 ms |
10104 KB |
ok, no valid answer |
94 |
Correct |
139 ms |
24372 KB |
ok, correct split |
95 |
Correct |
190 ms |
29232 KB |
ok, correct split |
96 |
Correct |
181 ms |
27572 KB |
ok, correct split |
97 |
Correct |
45 ms |
14460 KB |
ok, correct split |
98 |
Correct |
48 ms |
14588 KB |
ok, correct split |
99 |
Correct |
67 ms |
16804 KB |
ok, correct split |
100 |
Correct |
175 ms |
24688 KB |
ok, correct split |
101 |
Correct |
152 ms |
23640 KB |
ok, correct split |
102 |
Correct |
151 ms |
25196 KB |
ok, correct split |
103 |
Correct |
143 ms |
25448 KB |
ok, correct split |
104 |
Correct |
139 ms |
25172 KB |
ok, correct split |
105 |
Correct |
86 ms |
17620 KB |
ok, correct split |
106 |
Correct |
167 ms |
34648 KB |
ok, correct split |
107 |
Correct |
119 ms |
21476 KB |
ok, correct split |
108 |
Correct |
124 ms |
21352 KB |
ok, correct split |
109 |
Correct |
177 ms |
24288 KB |
ok, correct split |
110 |
Correct |
186 ms |
25576 KB |
ok, correct split |
111 |
Correct |
174 ms |
25320 KB |
ok, correct split |
112 |
Correct |
173 ms |
25704 KB |
ok, correct split |
113 |
Correct |
167 ms |
25712 KB |
ok, correct split |
114 |
Correct |
25 ms |
11768 KB |
ok, correct split |
115 |
Correct |
23 ms |
11512 KB |
ok, correct split |
116 |
Correct |
170 ms |
25456 KB |
ok, correct split |
117 |
Correct |
158 ms |
25072 KB |
ok, correct split |
118 |
Correct |
125 ms |
21304 KB |
ok, correct split |
119 |
Correct |
121 ms |
21104 KB |
ok, correct split |
120 |
Correct |
128 ms |
25320 KB |
ok, correct split |
121 |
Correct |
116 ms |
20600 KB |
ok, no valid answer |
122 |
Correct |
111 ms |
21848 KB |
ok, no valid answer |
123 |
Correct |
170 ms |
24312 KB |
ok, no valid answer |
124 |
Correct |
162 ms |
24444 KB |
ok, no valid answer |
125 |
Correct |
120 ms |
27240 KB |
ok, no valid answer |
126 |
Correct |
97 ms |
25708 KB |
ok, no valid answer |
127 |
Correct |
131 ms |
25064 KB |
ok, no valid answer |