#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
#include "../../../../MixedFunc/pretty_debug.h"
#else
#define debug(...) //ignore
#endif
struct stOrder {
vector<vi> g;
vi pre, low, P;
int Time;
vi preO;
stOrder(vector<vi> &g) : g(g), pre(sz(g),0), low(sz(g),0), P(sz(g),0) {}
int dfs(int at, int par) {
preO.eb(at);
P[at] = par;
pre[at] = ++Time;
low[at] = at;
trav(y, g[at]) if (y != par) {
int up = pre[y] ? y : dfs(y,at);
if(pre[up] < pre[low[at]]) low[at] = up;
}
return low[at];
}
vi order(int s){
dfs(s,-1);
int t = preO[1];
vector<list<int>::iterator> pos(sz(g));
list<int> L;
pos[s] = L.insert(L.end(), s);
pos[t] = L.insert(L.end(), t);
vi sign(sz(g));
sign[s] = -1;
rep(i,2,sz(g)) {
int x = preO[i];
auto it = pos[P[x]];
assert(sign[low[x]] != 0);
if(sign[low[x]] == 1) it++;
pos[x] = L.insert(it, x);
sign[P[x]] = -sign[low[x]];
}
rep(i,0,sz(g)) assert(*pos[i] == i);
return vi(all(L));
}
};
vi num, st, top;
vector<vector<pii>> ed;
int Time;
template<class F>
int dfs(int at, int par, F& f) {
int me = num[at] = ++Time, e, y, top = me;
trav(pa, ed[at]) if (pa.second != par) {
tie(y, e) = pa;
if (num[y]) {
top = min(top, num[y]);
if (num[y] < me) st.push_back(e);
} else {
int si = sz(st);
int up = dfs(y, e, f);
top = min(top, up);
if (up == me) {
st.push_back(e);
f(vi(st.begin() + si, st.end()));
st.resize(si);
}
else if (up < me) st.push_back(e);
else f({e}); // e is a bridge
}
}
return top;
}
template<class F>
void bicomps(F f) {
num.assign(sz(ed), 0);
rep(i,0,sz(ed)) if (!num[i]) dfs(i, -1, f);
}
const vi BAD{};
vector<int> find_split(int n, int a, int b, int c, vi p, vi q) {
debug(n,a,b,c);
debug(p);
debug(q);
// tries to find a split into 2 connected comps.
auto split = [&](){
// find split with side in [L,R] works.
int k = min({a,b,c});
int L = k, R = n-k;
debug(L,R);
ed.resize(n);
rep(i,0,sz(p)) {
ed[p[i]].emplace_back(q[i], i);
ed[q[i]].emplace_back(p[i], i);
}
vector<vi> cmpEd(n); // e-ids in component
vector<vi> bt(n); // block-tree(?): tree of verts and bcc, with edges between them.
bicomps([&](const vi& edg){
int C = sz(bt);
bt.eb();
cmpEd.eb(edg);
trav(i,edg) bt[C].eb(p[i]), bt[C].eb(q[i]);
sort(all(bt[C]));
bt[C].resize(unique(all(bt[C])) - bt[C].begin());
trav(i,bt[C]) bt[i].eb(C);
});
// precal subtree sizes
vi siz(sz(bt)), par(sz(bt));
function<int(int,int)> dfs = [&](int x, int p) {
par[x] = p;
if(x < n) ++siz[x];
trav(y, bt[x]) if(y != p) siz[x] += dfs(y, x);
return siz[x];
};
dfs(0,-1);
debug(siz);
auto comp = [&](int C) {
auto &cmp = bt[C];
int nc = sz(cmp);
debug(nc, cmp);
// build graph for bcc
unordered_map<int,int> toCmpId;
rep(i,0,nc) toCmpId[cmp[i]] = i;
vector<vi> G(nc);
trav(e, cmpEd[C]) {
int a = toCmpId[p[e]], b = toCmpId[q[e]];
G[a].eb(b);
G[b].eb(a);
}
// calculated sizes of subtrees routed at each node
vi ssz(nc,0);
int rt = -1;
rep(i,0,nc) {
int x = cmp[i];
if(par[x] == C) ssz[i] = siz[x];
else rt = i;
}
assert(rt != -1);
ssz[rt] = n - accumulate(all(ssz),0);
debug(ssz);
int mx = max_element(all(ssz)) - ssz.begin();
//int mn = (mx ? 0 : 1); // mn != mx.
if(ssz[mx] > R) return BAD;
// start building split
int S = 0, cnt = 0;
stOrder st(G);
vi sp = st.order(mx);
// now we extend S until S is in [L,R]
// Note: not sure bfs actually works for this?
while(S < L) S += ssz[sp[cnt++]];
assert(L <= S && S <= R);
sp.resize(cnt);
// construct answer
vi ans;
function<void(int,int)> dfs2 = [&](int x, int p) {
if(x < n) ans.eb(x);
trav(y, bt[x]) if(y != p) dfs2(y, x);
};
trav(i,sp) dfs2(cmp[i], C);
assert(sz(ans) == S);
return ans;
};
rep(C,n,sz(bt)) {
auto sp = comp(C);
if(sp != BAD) return sp;
}
return BAD;
};
vi sp = split();
if(sp == BAD) return vi(n,0);
debug(sp);
// find other side of split
sort(all(sp));
vi spC;
for(int i = 0, j = 0; i < n; ++i) {
if(j < sz(sp) && sp[j] == i) ++j;
else spC.eb(i);
}
if(sz(sp) > sz(spC)) swap(sp, spC);
// color vertices
vector<pii> Q = {{a,1}, {b,2}, {c,3}};
sort(all(Q));
vi res(n, Q[2].second);
auto color = [&](vi &vert, int sz, int col) {
assert(!vert.empty());
assert(sz <= sz(vert));
function<void(int)> f = [&](int x) {
if(!binary_search(all(vert), x)) return;
if(res[x] == col) return;
if(sz == 0) return;
res[x] = col; --sz;
trav(y, ed[x]) f(y.first);
};
f(vert[0]);
assert(sz == 0);
};
color(sp, Q[0].first, Q[0].second);
color(spC, Q[1].first, Q[1].second);
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
280 ms |
48048 KB |
ok, correct split |
8 |
Correct |
252 ms |
45800 KB |
ok, correct split |
9 |
Correct |
283 ms |
45860 KB |
ok, correct split |
10 |
Correct |
276 ms |
56428 KB |
ok, correct split |
11 |
Correct |
333 ms |
56328 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
252 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
230 ms |
33064 KB |
ok, correct split |
5 |
Correct |
282 ms |
30972 KB |
ok, correct split |
6 |
Correct |
285 ms |
56412 KB |
ok, correct split |
7 |
Correct |
286 ms |
45860 KB |
ok, correct split |
8 |
Correct |
297 ms |
27044 KB |
ok, correct split |
9 |
Correct |
195 ms |
20132 KB |
ok, correct split |
10 |
Correct |
209 ms |
31024 KB |
ok, correct split |
11 |
Correct |
214 ms |
30964 KB |
ok, correct split |
12 |
Correct |
218 ms |
31384 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
ok, correct split |
2 |
Correct |
341 ms |
30884 KB |
ok, correct split |
3 |
Correct |
88 ms |
12704 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
319 ms |
36364 KB |
ok, correct split |
6 |
Correct |
297 ms |
35748 KB |
ok, correct split |
7 |
Correct |
332 ms |
35360 KB |
ok, correct split |
8 |
Correct |
321 ms |
38536 KB |
ok, correct split |
9 |
Correct |
340 ms |
34924 KB |
ok, correct split |
10 |
Correct |
79 ms |
10200 KB |
ok, no valid answer |
11 |
Correct |
124 ms |
15124 KB |
ok, no valid answer |
12 |
Correct |
251 ms |
30360 KB |
ok, no valid answer |
13 |
Correct |
284 ms |
30116 KB |
ok, no valid answer |
14 |
Correct |
225 ms |
30572 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
256 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
256 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
2 ms |
376 KB |
ok, correct split |
8 |
Correct |
2 ms |
256 KB |
ok, correct split |
9 |
Correct |
8 ms |
1244 KB |
ok, correct split |
10 |
Correct |
7 ms |
1020 KB |
ok, correct split |
11 |
Correct |
3 ms |
376 KB |
ok, correct split |
12 |
Correct |
9 ms |
1400 KB |
ok, correct split |
13 |
Correct |
2 ms |
256 KB |
ok, correct split |
14 |
Correct |
2 ms |
256 KB |
ok, correct split |
15 |
Correct |
2 ms |
356 KB |
ok, correct split |
16 |
Correct |
2 ms |
376 KB |
ok, correct split |
17 |
Correct |
2 ms |
356 KB |
ok, correct split |
18 |
Correct |
2 ms |
256 KB |
ok, correct split |
19 |
Correct |
3 ms |
504 KB |
ok, correct split |
20 |
Correct |
4 ms |
760 KB |
ok, correct split |
21 |
Correct |
7 ms |
1144 KB |
ok, correct split |
22 |
Correct |
7 ms |
1144 KB |
ok, correct split |
23 |
Correct |
7 ms |
1272 KB |
ok, correct split |
24 |
Correct |
7 ms |
1144 KB |
ok, correct split |
25 |
Correct |
6 ms |
1144 KB |
ok, correct split |
26 |
Correct |
8 ms |
1528 KB |
ok, correct split |
27 |
Correct |
8 ms |
1528 KB |
ok, correct split |
28 |
Correct |
8 ms |
1392 KB |
ok, correct split |
29 |
Correct |
3 ms |
376 KB |
ok, correct split |
30 |
Correct |
7 ms |
1144 KB |
ok, correct split |
31 |
Correct |
3 ms |
504 KB |
ok, correct split |
32 |
Correct |
3 ms |
376 KB |
ok, correct split |
33 |
Correct |
3 ms |
504 KB |
ok, correct split |
34 |
Correct |
7 ms |
1144 KB |
ok, correct split |
35 |
Correct |
7 ms |
1016 KB |
ok, correct split |
36 |
Correct |
7 ms |
1016 KB |
ok, correct split |
37 |
Correct |
9 ms |
1532 KB |
ok, correct split |
38 |
Correct |
9 ms |
1528 KB |
ok, correct split |
39 |
Correct |
8 ms |
1528 KB |
ok, correct split |
40 |
Correct |
8 ms |
1528 KB |
ok, correct split |
41 |
Correct |
5 ms |
888 KB |
ok, correct split |
42 |
Correct |
5 ms |
888 KB |
ok, correct split |
43 |
Correct |
8 ms |
1528 KB |
ok, correct split |
44 |
Correct |
8 ms |
1528 KB |
ok, correct split |
45 |
Correct |
8 ms |
1528 KB |
ok, correct split |
46 |
Correct |
6 ms |
1144 KB |
ok, correct split |
47 |
Correct |
5 ms |
1016 KB |
ok, no valid answer |
48 |
Correct |
5 ms |
892 KB |
ok, correct split |
49 |
Correct |
6 ms |
1144 KB |
ok, correct split |
50 |
Correct |
2 ms |
256 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
256 KB |
ok, no valid answer |
52 |
Correct |
7 ms |
968 KB |
ok, no valid answer |
53 |
Correct |
7 ms |
1016 KB |
ok, no valid answer |
54 |
Correct |
6 ms |
1020 KB |
ok, no valid answer |
55 |
Correct |
7 ms |
888 KB |
ok, no valid answer |
56 |
Correct |
6 ms |
1016 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
280 ms |
48048 KB |
ok, correct split |
8 |
Correct |
252 ms |
45800 KB |
ok, correct split |
9 |
Correct |
283 ms |
45860 KB |
ok, correct split |
10 |
Correct |
276 ms |
56428 KB |
ok, correct split |
11 |
Correct |
333 ms |
56328 KB |
ok, correct split |
12 |
Correct |
2 ms |
252 KB |
ok, correct split |
13 |
Correct |
2 ms |
376 KB |
ok, correct split |
14 |
Correct |
2 ms |
376 KB |
ok, correct split |
15 |
Correct |
230 ms |
33064 KB |
ok, correct split |
16 |
Correct |
282 ms |
30972 KB |
ok, correct split |
17 |
Correct |
285 ms |
56412 KB |
ok, correct split |
18 |
Correct |
286 ms |
45860 KB |
ok, correct split |
19 |
Correct |
297 ms |
27044 KB |
ok, correct split |
20 |
Correct |
195 ms |
20132 KB |
ok, correct split |
21 |
Correct |
209 ms |
31024 KB |
ok, correct split |
22 |
Correct |
214 ms |
30964 KB |
ok, correct split |
23 |
Correct |
218 ms |
31384 KB |
ok, correct split |
24 |
Correct |
2 ms |
256 KB |
ok, correct split |
25 |
Correct |
341 ms |
30884 KB |
ok, correct split |
26 |
Correct |
88 ms |
12704 KB |
ok, correct split |
27 |
Correct |
2 ms |
376 KB |
ok, correct split |
28 |
Correct |
319 ms |
36364 KB |
ok, correct split |
29 |
Correct |
297 ms |
35748 KB |
ok, correct split |
30 |
Correct |
332 ms |
35360 KB |
ok, correct split |
31 |
Correct |
321 ms |
38536 KB |
ok, correct split |
32 |
Correct |
340 ms |
34924 KB |
ok, correct split |
33 |
Correct |
79 ms |
10200 KB |
ok, no valid answer |
34 |
Correct |
124 ms |
15124 KB |
ok, no valid answer |
35 |
Correct |
251 ms |
30360 KB |
ok, no valid answer |
36 |
Correct |
284 ms |
30116 KB |
ok, no valid answer |
37 |
Correct |
225 ms |
30572 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
256 KB |
ok, correct split |
39 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
256 KB |
ok, correct split |
41 |
Correct |
2 ms |
376 KB |
ok, correct split |
42 |
Correct |
2 ms |
256 KB |
ok, correct split |
43 |
Correct |
2 ms |
376 KB |
ok, correct split |
44 |
Correct |
2 ms |
376 KB |
ok, correct split |
45 |
Correct |
2 ms |
256 KB |
ok, correct split |
46 |
Correct |
8 ms |
1244 KB |
ok, correct split |
47 |
Correct |
7 ms |
1020 KB |
ok, correct split |
48 |
Correct |
3 ms |
376 KB |
ok, correct split |
49 |
Correct |
9 ms |
1400 KB |
ok, correct split |
50 |
Correct |
2 ms |
256 KB |
ok, correct split |
51 |
Correct |
2 ms |
256 KB |
ok, correct split |
52 |
Correct |
2 ms |
356 KB |
ok, correct split |
53 |
Correct |
2 ms |
376 KB |
ok, correct split |
54 |
Correct |
2 ms |
356 KB |
ok, correct split |
55 |
Correct |
2 ms |
256 KB |
ok, correct split |
56 |
Correct |
3 ms |
504 KB |
ok, correct split |
57 |
Correct |
4 ms |
760 KB |
ok, correct split |
58 |
Correct |
7 ms |
1144 KB |
ok, correct split |
59 |
Correct |
7 ms |
1144 KB |
ok, correct split |
60 |
Correct |
7 ms |
1272 KB |
ok, correct split |
61 |
Correct |
7 ms |
1144 KB |
ok, correct split |
62 |
Correct |
6 ms |
1144 KB |
ok, correct split |
63 |
Correct |
8 ms |
1528 KB |
ok, correct split |
64 |
Correct |
8 ms |
1528 KB |
ok, correct split |
65 |
Correct |
8 ms |
1392 KB |
ok, correct split |
66 |
Correct |
3 ms |
376 KB |
ok, correct split |
67 |
Correct |
7 ms |
1144 KB |
ok, correct split |
68 |
Correct |
3 ms |
504 KB |
ok, correct split |
69 |
Correct |
3 ms |
376 KB |
ok, correct split |
70 |
Correct |
3 ms |
504 KB |
ok, correct split |
71 |
Correct |
7 ms |
1144 KB |
ok, correct split |
72 |
Correct |
7 ms |
1016 KB |
ok, correct split |
73 |
Correct |
7 ms |
1016 KB |
ok, correct split |
74 |
Correct |
9 ms |
1532 KB |
ok, correct split |
75 |
Correct |
9 ms |
1528 KB |
ok, correct split |
76 |
Correct |
8 ms |
1528 KB |
ok, correct split |
77 |
Correct |
8 ms |
1528 KB |
ok, correct split |
78 |
Correct |
5 ms |
888 KB |
ok, correct split |
79 |
Correct |
5 ms |
888 KB |
ok, correct split |
80 |
Correct |
8 ms |
1528 KB |
ok, correct split |
81 |
Correct |
8 ms |
1528 KB |
ok, correct split |
82 |
Correct |
8 ms |
1528 KB |
ok, correct split |
83 |
Correct |
6 ms |
1144 KB |
ok, correct split |
84 |
Correct |
5 ms |
1016 KB |
ok, no valid answer |
85 |
Correct |
5 ms |
892 KB |
ok, correct split |
86 |
Correct |
6 ms |
1144 KB |
ok, correct split |
87 |
Correct |
2 ms |
256 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
256 KB |
ok, no valid answer |
89 |
Correct |
7 ms |
968 KB |
ok, no valid answer |
90 |
Correct |
7 ms |
1016 KB |
ok, no valid answer |
91 |
Correct |
6 ms |
1020 KB |
ok, no valid answer |
92 |
Correct |
7 ms |
888 KB |
ok, no valid answer |
93 |
Correct |
6 ms |
1016 KB |
ok, no valid answer |
94 |
Correct |
370 ms |
42296 KB |
ok, correct split |
95 |
Correct |
501 ms |
56868 KB |
ok, correct split |
96 |
Correct |
433 ms |
52816 KB |
ok, correct split |
97 |
Correct |
93 ms |
12576 KB |
ok, correct split |
98 |
Correct |
77 ms |
11116 KB |
ok, correct split |
99 |
Correct |
129 ms |
13624 KB |
ok, correct split |
100 |
Correct |
277 ms |
28572 KB |
ok, correct split |
101 |
Correct |
260 ms |
27444 KB |
ok, correct split |
102 |
Correct |
274 ms |
26920 KB |
ok, correct split |
103 |
Correct |
255 ms |
27292 KB |
ok, correct split |
104 |
Correct |
261 ms |
32360 KB |
ok, correct split |
105 |
Correct |
182 ms |
19188 KB |
ok, correct split |
106 |
Correct |
348 ms |
48152 KB |
ok, correct split |
107 |
Correct |
349 ms |
30608 KB |
ok, correct split |
108 |
Correct |
325 ms |
30440 KB |
ok, correct split |
109 |
Correct |
370 ms |
26764 KB |
ok, correct split |
110 |
Correct |
414 ms |
48640 KB |
ok, correct split |
111 |
Correct |
414 ms |
48768 KB |
ok, correct split |
112 |
Correct |
384 ms |
48256 KB |
ok, correct split |
113 |
Correct |
408 ms |
48132 KB |
ok, correct split |
114 |
Correct |
37 ms |
5920 KB |
ok, correct split |
115 |
Correct |
33 ms |
5408 KB |
ok, correct split |
116 |
Correct |
381 ms |
48492 KB |
ok, correct split |
117 |
Correct |
362 ms |
46912 KB |
ok, correct split |
118 |
Correct |
222 ms |
19592 KB |
ok, correct split |
119 |
Correct |
183 ms |
20260 KB |
ok, correct split |
120 |
Correct |
213 ms |
34492 KB |
ok, correct split |
121 |
Correct |
277 ms |
28316 KB |
ok, no valid answer |
122 |
Correct |
268 ms |
30112 KB |
ok, no valid answer |
123 |
Correct |
308 ms |
28068 KB |
ok, no valid answer |
124 |
Correct |
308 ms |
27556 KB |
ok, no valid answer |
125 |
Correct |
245 ms |
28564 KB |
ok, no valid answer |
126 |
Correct |
198 ms |
27484 KB |
ok, no valid answer |
127 |
Correct |
275 ms |
26640 KB |
ok, no valid answer |