#include <bits/stdc++.h>
#include "split.h"
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
const int NS = (int)2e5 + 4;
int n;
struct Dsu{
int n;
vector<int> pr, rk;
Dsu(int N):n(N){
pr.resize(n), rk.resize(n);
for(int i = 0; i < n; ++i) pr[i] = i, rk[i] = 1;
}
inline int get(int x){
return x == pr[x] ? x : pr[x] = get(pr[x]);
}
inline bool unite(int x, int y){
x = get(x), y = get(y);
if(x != y){
if(rk[x] < rk[y]) swap(x, y);
pr[y] = x, rk[x] += rk[y];
return true;
}
return false;
}
};
int ca, cb, cc;
vector<int> way[NS], wayt[NS];
int sz[NS], ans[NS], need;
Dsu gr(NS + 4);
void cdfs(int x, int pr){
for(auto&nxt:wayt[x]){
if(nxt == pr){
continue;
}
cdfs(nxt, x);
sz[x] += sz[nxt];
}
sz[x] += 1;
}
void col(int x, int pr){
for(auto&nxt:wayt[x]){
if(nxt == pr){
continue;
}
gr.unite(x, nxt);
col(nxt, x);
}
}
int cget(int x, int pr){
for(auto&nxt:wayt[x]){
if(nxt == pr){
continue;
}
if(sz[nxt] > n / 2){
return cget(nxt, x);
}
}
return x;
}
void adfs(int x, int tcol){
ans[x] = tcol; --need;
for(auto&nxt:wayt[x]){
if(!ans[nxt] && need){
adfs(nxt, tcol);
}
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> P, vector<int> q) {
ios_base::sync_with_stdio(false);
cin.tie(0);
n = N;
int m = (int)P.size();
ca = 1, cb = 2, cc = 3;
if(a > b) swap(a, b), swap(ca, cb);
if(a > c) swap(a, c), swap(ca, cc);
if(b > c) swap(b, c), swap(cb, cc);
Dsu span(n + 4);
for(int i = 1; i <= m; ++i){
int x, y; x = P[i - 1], y = q[i - 1]; ++x, ++y;
if(span.unite(x, y)){
wayt[x].push_back(y), wayt[y].push_back(x);
}
else way[x].push_back(y), way[y].push_back(x);
}
cdfs(1, -1);
int cent = cget(1, -1);
multiset<pair<int, int>> st;
for(auto&nxt:wayt[cent]){
col(nxt, cent);
st.insert({gr.rk[gr.get(nxt)], gr.get(nxt)});
}
for(int i = 1; i <= n; ++i){
for(auto&nxt:way[i]){
if(i == cent || nxt == cent){
continue;
}
auto p = st.end(); --p;
if(p->first >= a) break;
int pi = gr.get(i), pnxt = gr.get(nxt);
if(pi == pnxt) continue;
wayt[i].push_back(nxt), wayt[nxt].push_back(i);
auto si = st.find(make_pair(gr.rk[pi], pi));
auto snxt = st.find(make_pair(gr.rk[pnxt], pnxt));
gr.unite(pi, pnxt);
st.insert(make_pair(gr.rk[gr.get(pi)], gr.get(pi)));
st.erase(si), st.erase(snxt);
}
}
auto p = st.end(); --p;
if(p->first < a){
return vector<int>(n, 0);
}
ans[cent] = cb;
need = a;
adfs(p->second, ca);
need = b - 1;
for(auto&nxt:wayt[cent]){
if(!ans[nxt] && need){
adfs(nxt, cb);
}
}
for(int i = 1; i <= n; ++i){
if(!ans[i]) ans[i] = cc;
}
vector<int> rv(n);
for(int i = 0; i < n; ++i){
rv[i] = ans[i + 1];
}
return rv;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11220 KB |
ok, correct split |
2 |
Correct |
6 ms |
11220 KB |
ok, correct split |
3 |
Correct |
6 ms |
11276 KB |
ok, correct split |
4 |
Correct |
6 ms |
11228 KB |
ok, correct split |
5 |
Correct |
7 ms |
11284 KB |
ok, correct split |
6 |
Correct |
6 ms |
11220 KB |
ok, correct split |
7 |
Correct |
92 ms |
25356 KB |
ok, correct split |
8 |
Correct |
118 ms |
25360 KB |
ok, correct split |
9 |
Correct |
96 ms |
25244 KB |
ok, correct split |
10 |
Correct |
80 ms |
25364 KB |
ok, correct split |
11 |
Correct |
89 ms |
25284 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11288 KB |
ok, correct split |
2 |
Correct |
6 ms |
11220 KB |
ok, correct split |
3 |
Correct |
6 ms |
11220 KB |
ok, correct split |
4 |
Correct |
110 ms |
22396 KB |
ok, correct split |
5 |
Correct |
68 ms |
19216 KB |
ok, correct split |
6 |
Correct |
104 ms |
25332 KB |
ok, correct split |
7 |
Correct |
90 ms |
25352 KB |
ok, correct split |
8 |
Correct |
117 ms |
24312 KB |
ok, correct split |
9 |
Correct |
73 ms |
19152 KB |
ok, correct split |
10 |
Correct |
87 ms |
23712 KB |
ok, correct split |
11 |
Correct |
98 ms |
23748 KB |
ok, correct split |
12 |
Correct |
112 ms |
24224 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
11236 KB |
ok, correct split |
2 |
Correct |
72 ms |
19216 KB |
ok, correct split |
3 |
Correct |
28 ms |
14440 KB |
ok, correct split |
4 |
Correct |
6 ms |
11220 KB |
ok, correct split |
5 |
Correct |
116 ms |
22848 KB |
ok, correct split |
6 |
Correct |
89 ms |
22812 KB |
ok, correct split |
7 |
Correct |
97 ms |
22732 KB |
ok, correct split |
8 |
Correct |
86 ms |
22796 KB |
ok, correct split |
9 |
Correct |
117 ms |
22820 KB |
ok, correct split |
10 |
Correct |
25 ms |
13836 KB |
ok, no valid answer |
11 |
Correct |
34 ms |
15060 KB |
ok, no valid answer |
12 |
Correct |
90 ms |
21896 KB |
ok, no valid answer |
13 |
Correct |
88 ms |
19228 KB |
ok, no valid answer |
14 |
Correct |
92 ms |
23904 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11284 KB |
ok, correct split |
2 |
Correct |
6 ms |
11220 KB |
ok, no valid answer |
3 |
Correct |
6 ms |
11220 KB |
ok, correct split |
4 |
Correct |
6 ms |
11220 KB |
ok, correct split |
5 |
Correct |
7 ms |
11220 KB |
ok, correct split |
6 |
Correct |
6 ms |
11220 KB |
ok, correct split |
7 |
Correct |
6 ms |
11220 KB |
ok, correct split |
8 |
Correct |
6 ms |
11220 KB |
ok, correct split |
9 |
Correct |
8 ms |
11548 KB |
ok, correct split |
10 |
Correct |
8 ms |
11548 KB |
ok, correct split |
11 |
Correct |
8 ms |
11288 KB |
ok, correct split |
12 |
Correct |
9 ms |
11680 KB |
ok, correct split |
13 |
Correct |
6 ms |
11220 KB |
ok, correct split |
14 |
Correct |
6 ms |
11220 KB |
ok, correct split |
15 |
Correct |
6 ms |
11292 KB |
ok, correct split |
16 |
Correct |
6 ms |
11288 KB |
ok, correct split |
17 |
Correct |
7 ms |
11220 KB |
ok, correct split |
18 |
Correct |
6 ms |
11288 KB |
ok, correct split |
19 |
Correct |
8 ms |
11220 KB |
ok, correct split |
20 |
Correct |
6 ms |
11348 KB |
ok, correct split |
21 |
Correct |
9 ms |
11476 KB |
ok, correct split |
22 |
Correct |
8 ms |
11556 KB |
ok, correct split |
23 |
Correct |
10 ms |
11556 KB |
ok, correct split |
24 |
Correct |
8 ms |
11604 KB |
ok, correct split |
25 |
Correct |
9 ms |
11476 KB |
ok, correct split |
26 |
Correct |
11 ms |
11636 KB |
ok, correct split |
27 |
Correct |
8 ms |
11620 KB |
ok, correct split |
28 |
Correct |
8 ms |
11660 KB |
ok, correct split |
29 |
Correct |
6 ms |
11348 KB |
ok, correct split |
30 |
Correct |
9 ms |
11676 KB |
ok, correct split |
31 |
Correct |
8 ms |
11348 KB |
ok, correct split |
32 |
Correct |
7 ms |
11332 KB |
ok, correct split |
33 |
Correct |
8 ms |
11316 KB |
ok, correct split |
34 |
Correct |
9 ms |
11476 KB |
ok, correct split |
35 |
Correct |
8 ms |
11560 KB |
ok, correct split |
36 |
Correct |
8 ms |
11476 KB |
ok, correct split |
37 |
Correct |
9 ms |
11604 KB |
ok, correct split |
38 |
Correct |
11 ms |
11604 KB |
ok, correct split |
39 |
Correct |
9 ms |
11636 KB |
ok, correct split |
40 |
Correct |
8 ms |
11604 KB |
ok, correct split |
41 |
Correct |
8 ms |
11452 KB |
ok, correct split |
42 |
Correct |
10 ms |
11488 KB |
ok, correct split |
43 |
Correct |
8 ms |
11604 KB |
ok, correct split |
44 |
Correct |
8 ms |
11620 KB |
ok, correct split |
45 |
Correct |
8 ms |
11620 KB |
ok, correct split |
46 |
Correct |
8 ms |
11732 KB |
ok, correct split |
47 |
Correct |
7 ms |
11476 KB |
ok, no valid answer |
48 |
Correct |
7 ms |
11432 KB |
ok, correct split |
49 |
Correct |
7 ms |
11556 KB |
ok, correct split |
50 |
Correct |
8 ms |
11312 KB |
ok, no valid answer |
51 |
Correct |
7 ms |
11220 KB |
ok, no valid answer |
52 |
Correct |
9 ms |
11476 KB |
ok, no valid answer |
53 |
Correct |
8 ms |
11604 KB |
ok, no valid answer |
54 |
Correct |
7 ms |
11604 KB |
ok, no valid answer |
55 |
Correct |
8 ms |
11604 KB |
ok, no valid answer |
56 |
Correct |
7 ms |
11548 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11220 KB |
ok, correct split |
2 |
Correct |
6 ms |
11220 KB |
ok, correct split |
3 |
Correct |
6 ms |
11276 KB |
ok, correct split |
4 |
Correct |
6 ms |
11228 KB |
ok, correct split |
5 |
Correct |
7 ms |
11284 KB |
ok, correct split |
6 |
Correct |
6 ms |
11220 KB |
ok, correct split |
7 |
Correct |
92 ms |
25356 KB |
ok, correct split |
8 |
Correct |
118 ms |
25360 KB |
ok, correct split |
9 |
Correct |
96 ms |
25244 KB |
ok, correct split |
10 |
Correct |
80 ms |
25364 KB |
ok, correct split |
11 |
Correct |
89 ms |
25284 KB |
ok, correct split |
12 |
Correct |
6 ms |
11288 KB |
ok, correct split |
13 |
Correct |
6 ms |
11220 KB |
ok, correct split |
14 |
Correct |
6 ms |
11220 KB |
ok, correct split |
15 |
Correct |
110 ms |
22396 KB |
ok, correct split |
16 |
Correct |
68 ms |
19216 KB |
ok, correct split |
17 |
Correct |
104 ms |
25332 KB |
ok, correct split |
18 |
Correct |
90 ms |
25352 KB |
ok, correct split |
19 |
Correct |
117 ms |
24312 KB |
ok, correct split |
20 |
Correct |
73 ms |
19152 KB |
ok, correct split |
21 |
Correct |
87 ms |
23712 KB |
ok, correct split |
22 |
Correct |
98 ms |
23748 KB |
ok, correct split |
23 |
Correct |
112 ms |
24224 KB |
ok, correct split |
24 |
Correct |
9 ms |
11236 KB |
ok, correct split |
25 |
Correct |
72 ms |
19216 KB |
ok, correct split |
26 |
Correct |
28 ms |
14440 KB |
ok, correct split |
27 |
Correct |
6 ms |
11220 KB |
ok, correct split |
28 |
Correct |
116 ms |
22848 KB |
ok, correct split |
29 |
Correct |
89 ms |
22812 KB |
ok, correct split |
30 |
Correct |
97 ms |
22732 KB |
ok, correct split |
31 |
Correct |
86 ms |
22796 KB |
ok, correct split |
32 |
Correct |
117 ms |
22820 KB |
ok, correct split |
33 |
Correct |
25 ms |
13836 KB |
ok, no valid answer |
34 |
Correct |
34 ms |
15060 KB |
ok, no valid answer |
35 |
Correct |
90 ms |
21896 KB |
ok, no valid answer |
36 |
Correct |
88 ms |
19228 KB |
ok, no valid answer |
37 |
Correct |
92 ms |
23904 KB |
ok, no valid answer |
38 |
Correct |
6 ms |
11284 KB |
ok, correct split |
39 |
Correct |
6 ms |
11220 KB |
ok, no valid answer |
40 |
Correct |
6 ms |
11220 KB |
ok, correct split |
41 |
Correct |
6 ms |
11220 KB |
ok, correct split |
42 |
Correct |
7 ms |
11220 KB |
ok, correct split |
43 |
Correct |
6 ms |
11220 KB |
ok, correct split |
44 |
Correct |
6 ms |
11220 KB |
ok, correct split |
45 |
Correct |
6 ms |
11220 KB |
ok, correct split |
46 |
Correct |
8 ms |
11548 KB |
ok, correct split |
47 |
Correct |
8 ms |
11548 KB |
ok, correct split |
48 |
Correct |
8 ms |
11288 KB |
ok, correct split |
49 |
Correct |
9 ms |
11680 KB |
ok, correct split |
50 |
Correct |
6 ms |
11220 KB |
ok, correct split |
51 |
Correct |
6 ms |
11220 KB |
ok, correct split |
52 |
Correct |
6 ms |
11292 KB |
ok, correct split |
53 |
Correct |
6 ms |
11288 KB |
ok, correct split |
54 |
Correct |
7 ms |
11220 KB |
ok, correct split |
55 |
Correct |
6 ms |
11288 KB |
ok, correct split |
56 |
Correct |
8 ms |
11220 KB |
ok, correct split |
57 |
Correct |
6 ms |
11348 KB |
ok, correct split |
58 |
Correct |
9 ms |
11476 KB |
ok, correct split |
59 |
Correct |
8 ms |
11556 KB |
ok, correct split |
60 |
Correct |
10 ms |
11556 KB |
ok, correct split |
61 |
Correct |
8 ms |
11604 KB |
ok, correct split |
62 |
Correct |
9 ms |
11476 KB |
ok, correct split |
63 |
Correct |
11 ms |
11636 KB |
ok, correct split |
64 |
Correct |
8 ms |
11620 KB |
ok, correct split |
65 |
Correct |
8 ms |
11660 KB |
ok, correct split |
66 |
Correct |
6 ms |
11348 KB |
ok, correct split |
67 |
Correct |
9 ms |
11676 KB |
ok, correct split |
68 |
Correct |
8 ms |
11348 KB |
ok, correct split |
69 |
Correct |
7 ms |
11332 KB |
ok, correct split |
70 |
Correct |
8 ms |
11316 KB |
ok, correct split |
71 |
Correct |
9 ms |
11476 KB |
ok, correct split |
72 |
Correct |
8 ms |
11560 KB |
ok, correct split |
73 |
Correct |
8 ms |
11476 KB |
ok, correct split |
74 |
Correct |
9 ms |
11604 KB |
ok, correct split |
75 |
Correct |
11 ms |
11604 KB |
ok, correct split |
76 |
Correct |
9 ms |
11636 KB |
ok, correct split |
77 |
Correct |
8 ms |
11604 KB |
ok, correct split |
78 |
Correct |
8 ms |
11452 KB |
ok, correct split |
79 |
Correct |
10 ms |
11488 KB |
ok, correct split |
80 |
Correct |
8 ms |
11604 KB |
ok, correct split |
81 |
Correct |
8 ms |
11620 KB |
ok, correct split |
82 |
Correct |
8 ms |
11620 KB |
ok, correct split |
83 |
Correct |
8 ms |
11732 KB |
ok, correct split |
84 |
Correct |
7 ms |
11476 KB |
ok, no valid answer |
85 |
Correct |
7 ms |
11432 KB |
ok, correct split |
86 |
Correct |
7 ms |
11556 KB |
ok, correct split |
87 |
Correct |
8 ms |
11312 KB |
ok, no valid answer |
88 |
Correct |
7 ms |
11220 KB |
ok, no valid answer |
89 |
Correct |
9 ms |
11476 KB |
ok, no valid answer |
90 |
Correct |
8 ms |
11604 KB |
ok, no valid answer |
91 |
Correct |
7 ms |
11604 KB |
ok, no valid answer |
92 |
Correct |
8 ms |
11604 KB |
ok, no valid answer |
93 |
Correct |
7 ms |
11548 KB |
ok, no valid answer |
94 |
Correct |
96 ms |
20724 KB |
ok, correct split |
95 |
Correct |
124 ms |
24652 KB |
ok, correct split |
96 |
Correct |
120 ms |
23360 KB |
ok, correct split |
97 |
Correct |
27 ms |
14448 KB |
ok, correct split |
98 |
Correct |
32 ms |
14796 KB |
ok, correct split |
99 |
Correct |
58 ms |
16868 KB |
ok, correct split |
100 |
Correct |
114 ms |
24736 KB |
ok, correct split |
101 |
Correct |
108 ms |
23516 KB |
ok, correct split |
102 |
Correct |
140 ms |
26428 KB |
ok, correct split |
103 |
Correct |
145 ms |
26364 KB |
ok, correct split |
104 |
Correct |
124 ms |
26584 KB |
ok, correct split |
105 |
Correct |
49 ms |
16508 KB |
ok, correct split |
106 |
Correct |
114 ms |
28008 KB |
ok, correct split |
107 |
Correct |
79 ms |
19280 KB |
ok, correct split |
108 |
Correct |
67 ms |
19208 KB |
ok, correct split |
109 |
Correct |
127 ms |
24448 KB |
ok, correct split |
110 |
Correct |
197 ms |
27424 KB |
ok, correct split |
111 |
Correct |
183 ms |
27420 KB |
ok, correct split |
112 |
Correct |
209 ms |
27428 KB |
ok, correct split |
113 |
Correct |
170 ms |
27412 KB |
ok, correct split |
114 |
Correct |
16 ms |
12884 KB |
ok, correct split |
115 |
Correct |
17 ms |
12824 KB |
ok, correct split |
116 |
Correct |
158 ms |
27292 KB |
ok, correct split |
117 |
Correct |
122 ms |
26888 KB |
ok, correct split |
118 |
Correct |
110 ms |
19196 KB |
ok, correct split |
119 |
Correct |
99 ms |
19200 KB |
ok, correct split |
120 |
Correct |
110 ms |
22368 KB |
ok, correct split |
121 |
Correct |
74 ms |
19020 KB |
ok, no valid answer |
122 |
Correct |
90 ms |
19816 KB |
ok, no valid answer |
123 |
Correct |
130 ms |
24208 KB |
ok, no valid answer |
124 |
Correct |
184 ms |
24396 KB |
ok, no valid answer |
125 |
Correct |
116 ms |
24772 KB |
ok, no valid answer |
126 |
Correct |
93 ms |
22508 KB |
ok, no valid answer |
127 |
Correct |
172 ms |
25672 KB |
ok, no valid answer |