#include "split.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#define N_ 201000
using namespace std;
vector<int>E[N_], T[N_], GP[N_], G[N_];
int n, AA, BB, CC, par[N_], vis[N_], C[N_], Where[N_], chk[N_];
void DFS1(int a) {
vis[a] = 1;
C[a] = 1;
for (auto &x : E[a]) {
if (vis[x]) continue;
par[x] = a;
T[a].push_back(x);
T[x].push_back(a);
DFS1(x);
C[a] += C[x];
}
}
int M1=1, M2=2, M3=3;
vector<int>TP;
void DFS2(int a, int pp) {
TP.push_back(a);
for (auto &x : T[a]) {
if (x == pp)continue;
DFS2(x, a);
}
}
void DFS3(int a, int pp, int ppp) {
GP[ppp].push_back(a);
Where[a] = ppp;
C[a] = 1;
for (auto &x : T[a]) {
if (x != pp) {
DFS3(x, a, ppp);
C[a] += C[x];
}
}
}
int val[N_], szlim;
void DFS4(int a){
vis[a] = 1;
if (szlim) {
TP.push_back(a);
szlim--;
}
for (auto &x : E[a]) {
if (val[x] && !vis[x])DFS4(x);
}
}
vector<int>Conn(vector<int> A, int num) {
int i;
for (i = 1; i <= n; i++)val[i] = 0, vis[i] = 0;
for (auto &x : A)val[x] = 1;
TP.clear();
szlim = num;
DFS4(A[0]);
return TP;
}
vector<int> Remaining(vector<int> A) {
int i;
for (i = 1; i <= n; i++)vis[i] = 0;
for (auto &x : A)vis[x] = 1;
vector<int>res;
for (i = 1; i <= n; i++)if (!vis[i])res.push_back(i);
return res;
}
vector<int>MakeAns(vector<int>A, vector<int>B) {
if (A.size() > B.size()) {
swap(A, B);
}
A = Conn(A, AA);
B = Conn(B, BB);
vector<int>res(n);
for (int i = 0; i < n; i++)res[i] = M3;
for (auto &x : A)res[x-1] = M1;
for (auto &x : B)res[x-1] = M2;
return res;
}
int sum;
void Go(int a) {
vis[a] = 1;
TP.push_back(a);
sum += C[a];
if (sum >= AA)return;
for (auto &x : G[a]) {
if (!vis[x]) {
Go(x);
if (sum >= AA)return;
}
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
if (a > b)swap(a, b),swap(M1,M2);
if (a > c)swap(a, c),swap(M1,M3);
if (b > c)swap(b, c),swap(M2,M3);
AA = a, BB = b, CC = c;
int i;
for (i = 0; i < p.size(); i++) {
E[p[i]+1].push_back(q[i]+1);
E[q[i]+1].push_back(p[i]+1);
}
DFS1(1);
for (i = 1; i <= n; i++) {
if ((C[i] >= AA && n - C[i] >= BB)|| (C[i] >= BB && n - C[i] >= AA)) {
TP.clear();
DFS2(i, par[i]);
vector<int>TP2 = Remaining(TP);
return MakeAns(TP, TP2);
}
}
int Mn = 1e9, mid = -1;
for (i = 1; i <= n; i++) {
if (Mn > C[i] && C[i] * 2 > n)Mn = C[i], mid = i;
}
for (auto &x : T[mid]) {
chk[x] = 1;
DFS3(x, mid, x);
}
for (i = 1; i <= n; i++) {
for (auto &x : E[i]) {
if (i == mid || x == mid)continue;
if (Where[i] != Where[x]) {
G[Where[i]].push_back(Where[x]);
}
}
}
for (i = 1; i <= n; i++)vis[i] = 0;
for (auto &t : T[mid]) {
sum = 0;
TP.clear();
Go(T[mid][0]);
if (sum >= AA) {
vector<int>TT;
for (auto &tt : TP) {
for (auto &x : GP[tt]) {
TT.push_back(x);
}
}
return MakeAns(TT, Remaining(TT));
}
}
vector<int>res(n);
return res;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < p.size(); i++) {
~~^~~~~~~~~~
split.cpp:148:13: warning: unused variable 't' [-Wunused-variable]
for (auto &t : T[mid]) {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
19192 KB |
ok, correct split |
2 |
Correct |
19 ms |
19192 KB |
ok, correct split |
3 |
Correct |
19 ms |
19192 KB |
ok, correct split |
4 |
Correct |
19 ms |
19192 KB |
ok, correct split |
5 |
Correct |
20 ms |
19064 KB |
ok, correct split |
6 |
Correct |
62 ms |
19192 KB |
ok, correct split |
7 |
Correct |
182 ms |
34424 KB |
ok, correct split |
8 |
Correct |
168 ms |
33120 KB |
ok, correct split |
9 |
Correct |
167 ms |
32892 KB |
ok, correct split |
10 |
Correct |
173 ms |
34620 KB |
ok, correct split |
11 |
Correct |
177 ms |
34580 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
19192 KB |
ok, correct split |
2 |
Correct |
23 ms |
19192 KB |
ok, correct split |
3 |
Correct |
23 ms |
19192 KB |
ok, correct split |
4 |
Correct |
195 ms |
33136 KB |
ok, correct split |
5 |
Correct |
143 ms |
30388 KB |
ok, correct split |
6 |
Correct |
169 ms |
34672 KB |
ok, correct split |
7 |
Correct |
177 ms |
32984 KB |
ok, correct split |
8 |
Correct |
187 ms |
32116 KB |
ok, correct split |
9 |
Correct |
159 ms |
30404 KB |
ok, correct split |
10 |
Correct |
118 ms |
31088 KB |
ok, correct split |
11 |
Correct |
117 ms |
30732 KB |
ok, correct split |
12 |
Correct |
110 ms |
31048 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
19192 KB |
ok, correct split |
2 |
Correct |
149 ms |
30236 KB |
ok, correct split |
3 |
Correct |
71 ms |
23672 KB |
ok, correct split |
4 |
Correct |
19 ms |
19192 KB |
ok, correct split |
5 |
Correct |
170 ms |
31600 KB |
ok, correct split |
6 |
Correct |
173 ms |
31472 KB |
ok, correct split |
7 |
Correct |
178 ms |
31464 KB |
ok, correct split |
8 |
Correct |
168 ms |
32112 KB |
ok, correct split |
9 |
Correct |
178 ms |
31344 KB |
ok, correct split |
10 |
Correct |
63 ms |
23032 KB |
ok, no valid answer |
11 |
Correct |
71 ms |
24696 KB |
ok, no valid answer |
12 |
Correct |
137 ms |
32116 KB |
ok, no valid answer |
13 |
Correct |
149 ms |
30428 KB |
ok, no valid answer |
14 |
Correct |
131 ms |
33236 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
19164 KB |
ok, correct split |
2 |
Correct |
23 ms |
19252 KB |
ok, no valid answer |
3 |
Correct |
20 ms |
19196 KB |
ok, correct split |
4 |
Correct |
29 ms |
19192 KB |
ok, correct split |
5 |
Correct |
20 ms |
19192 KB |
ok, correct split |
6 |
Correct |
19 ms |
19192 KB |
ok, correct split |
7 |
Correct |
19 ms |
19192 KB |
ok, correct split |
8 |
Correct |
19 ms |
19192 KB |
ok, correct split |
9 |
Correct |
22 ms |
19576 KB |
ok, correct split |
10 |
Correct |
23 ms |
19576 KB |
ok, correct split |
11 |
Correct |
19 ms |
19192 KB |
ok, correct split |
12 |
Correct |
22 ms |
19576 KB |
ok, correct split |
13 |
Correct |
19 ms |
19192 KB |
ok, correct split |
14 |
Correct |
19 ms |
19192 KB |
ok, correct split |
15 |
Correct |
19 ms |
19192 KB |
ok, correct split |
16 |
Correct |
19 ms |
19192 KB |
ok, correct split |
17 |
Correct |
19 ms |
19192 KB |
ok, correct split |
18 |
Correct |
20 ms |
19192 KB |
ok, correct split |
19 |
Correct |
20 ms |
19320 KB |
ok, correct split |
20 |
Correct |
21 ms |
19320 KB |
ok, correct split |
21 |
Correct |
22 ms |
19576 KB |
ok, correct split |
22 |
Correct |
22 ms |
19448 KB |
ok, correct split |
23 |
Correct |
21 ms |
19576 KB |
ok, correct split |
24 |
Correct |
22 ms |
19576 KB |
ok, correct split |
25 |
Correct |
22 ms |
19576 KB |
ok, correct split |
26 |
Correct |
21 ms |
19704 KB |
ok, correct split |
27 |
Correct |
28 ms |
19704 KB |
ok, correct split |
28 |
Correct |
22 ms |
19676 KB |
ok, correct split |
29 |
Correct |
19 ms |
19292 KB |
ok, correct split |
30 |
Correct |
25 ms |
19576 KB |
ok, correct split |
31 |
Correct |
20 ms |
19320 KB |
ok, correct split |
32 |
Correct |
20 ms |
19320 KB |
ok, correct split |
33 |
Correct |
19 ms |
19292 KB |
ok, correct split |
34 |
Correct |
22 ms |
19576 KB |
ok, correct split |
35 |
Correct |
22 ms |
19576 KB |
ok, correct split |
36 |
Correct |
21 ms |
19576 KB |
ok, correct split |
37 |
Correct |
23 ms |
19580 KB |
ok, correct split |
38 |
Correct |
23 ms |
19576 KB |
ok, correct split |
39 |
Correct |
22 ms |
19580 KB |
ok, correct split |
40 |
Correct |
22 ms |
19576 KB |
ok, correct split |
41 |
Correct |
25 ms |
19324 KB |
ok, correct split |
42 |
Correct |
25 ms |
19320 KB |
ok, correct split |
43 |
Correct |
28 ms |
19576 KB |
ok, correct split |
44 |
Correct |
26 ms |
19576 KB |
ok, correct split |
45 |
Correct |
26 ms |
19576 KB |
ok, correct split |
46 |
Correct |
25 ms |
19448 KB |
ok, correct split |
47 |
Correct |
26 ms |
19576 KB |
ok, no valid answer |
48 |
Correct |
22 ms |
19576 KB |
ok, correct split |
49 |
Correct |
21 ms |
19576 KB |
ok, correct split |
50 |
Correct |
19 ms |
19192 KB |
ok, no valid answer |
51 |
Correct |
19 ms |
19192 KB |
ok, no valid answer |
52 |
Correct |
21 ms |
19448 KB |
ok, no valid answer |
53 |
Correct |
26 ms |
19576 KB |
ok, no valid answer |
54 |
Correct |
27 ms |
19576 KB |
ok, no valid answer |
55 |
Correct |
27 ms |
19576 KB |
ok, no valid answer |
56 |
Correct |
24 ms |
19576 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
19192 KB |
ok, correct split |
2 |
Correct |
19 ms |
19192 KB |
ok, correct split |
3 |
Correct |
19 ms |
19192 KB |
ok, correct split |
4 |
Correct |
19 ms |
19192 KB |
ok, correct split |
5 |
Correct |
20 ms |
19064 KB |
ok, correct split |
6 |
Correct |
62 ms |
19192 KB |
ok, correct split |
7 |
Correct |
182 ms |
34424 KB |
ok, correct split |
8 |
Correct |
168 ms |
33120 KB |
ok, correct split |
9 |
Correct |
167 ms |
32892 KB |
ok, correct split |
10 |
Correct |
173 ms |
34620 KB |
ok, correct split |
11 |
Correct |
177 ms |
34580 KB |
ok, correct split |
12 |
Correct |
23 ms |
19192 KB |
ok, correct split |
13 |
Correct |
23 ms |
19192 KB |
ok, correct split |
14 |
Correct |
23 ms |
19192 KB |
ok, correct split |
15 |
Correct |
195 ms |
33136 KB |
ok, correct split |
16 |
Correct |
143 ms |
30388 KB |
ok, correct split |
17 |
Correct |
169 ms |
34672 KB |
ok, correct split |
18 |
Correct |
177 ms |
32984 KB |
ok, correct split |
19 |
Correct |
187 ms |
32116 KB |
ok, correct split |
20 |
Correct |
159 ms |
30404 KB |
ok, correct split |
21 |
Correct |
118 ms |
31088 KB |
ok, correct split |
22 |
Correct |
117 ms |
30732 KB |
ok, correct split |
23 |
Correct |
110 ms |
31048 KB |
ok, correct split |
24 |
Correct |
18 ms |
19192 KB |
ok, correct split |
25 |
Correct |
149 ms |
30236 KB |
ok, correct split |
26 |
Correct |
71 ms |
23672 KB |
ok, correct split |
27 |
Correct |
19 ms |
19192 KB |
ok, correct split |
28 |
Correct |
170 ms |
31600 KB |
ok, correct split |
29 |
Correct |
173 ms |
31472 KB |
ok, correct split |
30 |
Correct |
178 ms |
31464 KB |
ok, correct split |
31 |
Correct |
168 ms |
32112 KB |
ok, correct split |
32 |
Correct |
178 ms |
31344 KB |
ok, correct split |
33 |
Correct |
63 ms |
23032 KB |
ok, no valid answer |
34 |
Correct |
71 ms |
24696 KB |
ok, no valid answer |
35 |
Correct |
137 ms |
32116 KB |
ok, no valid answer |
36 |
Correct |
149 ms |
30428 KB |
ok, no valid answer |
37 |
Correct |
131 ms |
33236 KB |
ok, no valid answer |
38 |
Correct |
24 ms |
19164 KB |
ok, correct split |
39 |
Correct |
23 ms |
19252 KB |
ok, no valid answer |
40 |
Correct |
20 ms |
19196 KB |
ok, correct split |
41 |
Correct |
29 ms |
19192 KB |
ok, correct split |
42 |
Correct |
20 ms |
19192 KB |
ok, correct split |
43 |
Correct |
19 ms |
19192 KB |
ok, correct split |
44 |
Correct |
19 ms |
19192 KB |
ok, correct split |
45 |
Correct |
19 ms |
19192 KB |
ok, correct split |
46 |
Correct |
22 ms |
19576 KB |
ok, correct split |
47 |
Correct |
23 ms |
19576 KB |
ok, correct split |
48 |
Correct |
19 ms |
19192 KB |
ok, correct split |
49 |
Correct |
22 ms |
19576 KB |
ok, correct split |
50 |
Correct |
19 ms |
19192 KB |
ok, correct split |
51 |
Correct |
19 ms |
19192 KB |
ok, correct split |
52 |
Correct |
19 ms |
19192 KB |
ok, correct split |
53 |
Correct |
19 ms |
19192 KB |
ok, correct split |
54 |
Correct |
19 ms |
19192 KB |
ok, correct split |
55 |
Correct |
20 ms |
19192 KB |
ok, correct split |
56 |
Correct |
20 ms |
19320 KB |
ok, correct split |
57 |
Correct |
21 ms |
19320 KB |
ok, correct split |
58 |
Correct |
22 ms |
19576 KB |
ok, correct split |
59 |
Correct |
22 ms |
19448 KB |
ok, correct split |
60 |
Correct |
21 ms |
19576 KB |
ok, correct split |
61 |
Correct |
22 ms |
19576 KB |
ok, correct split |
62 |
Correct |
22 ms |
19576 KB |
ok, correct split |
63 |
Correct |
21 ms |
19704 KB |
ok, correct split |
64 |
Correct |
28 ms |
19704 KB |
ok, correct split |
65 |
Correct |
22 ms |
19676 KB |
ok, correct split |
66 |
Correct |
19 ms |
19292 KB |
ok, correct split |
67 |
Correct |
25 ms |
19576 KB |
ok, correct split |
68 |
Correct |
20 ms |
19320 KB |
ok, correct split |
69 |
Correct |
20 ms |
19320 KB |
ok, correct split |
70 |
Correct |
19 ms |
19292 KB |
ok, correct split |
71 |
Correct |
22 ms |
19576 KB |
ok, correct split |
72 |
Correct |
22 ms |
19576 KB |
ok, correct split |
73 |
Correct |
21 ms |
19576 KB |
ok, correct split |
74 |
Correct |
23 ms |
19580 KB |
ok, correct split |
75 |
Correct |
23 ms |
19576 KB |
ok, correct split |
76 |
Correct |
22 ms |
19580 KB |
ok, correct split |
77 |
Correct |
22 ms |
19576 KB |
ok, correct split |
78 |
Correct |
25 ms |
19324 KB |
ok, correct split |
79 |
Correct |
25 ms |
19320 KB |
ok, correct split |
80 |
Correct |
28 ms |
19576 KB |
ok, correct split |
81 |
Correct |
26 ms |
19576 KB |
ok, correct split |
82 |
Correct |
26 ms |
19576 KB |
ok, correct split |
83 |
Correct |
25 ms |
19448 KB |
ok, correct split |
84 |
Correct |
26 ms |
19576 KB |
ok, no valid answer |
85 |
Correct |
22 ms |
19576 KB |
ok, correct split |
86 |
Correct |
21 ms |
19576 KB |
ok, correct split |
87 |
Correct |
19 ms |
19192 KB |
ok, no valid answer |
88 |
Correct |
19 ms |
19192 KB |
ok, no valid answer |
89 |
Correct |
21 ms |
19448 KB |
ok, no valid answer |
90 |
Correct |
26 ms |
19576 KB |
ok, no valid answer |
91 |
Correct |
27 ms |
19576 KB |
ok, no valid answer |
92 |
Correct |
27 ms |
19576 KB |
ok, no valid answer |
93 |
Correct |
24 ms |
19576 KB |
ok, no valid answer |
94 |
Correct |
173 ms |
31848 KB |
ok, correct split |
95 |
Correct |
228 ms |
34996 KB |
ok, correct split |
96 |
Correct |
193 ms |
33896 KB |
ok, correct split |
97 |
Correct |
63 ms |
23800 KB |
ok, correct split |
98 |
Correct |
78 ms |
23672 KB |
ok, correct split |
99 |
Correct |
88 ms |
24952 KB |
ok, correct split |
100 |
Correct |
199 ms |
32496 KB |
ok, correct split |
101 |
Correct |
198 ms |
31856 KB |
ok, correct split |
102 |
Correct |
182 ms |
31952 KB |
ok, correct split |
103 |
Correct |
168 ms |
31444 KB |
ok, correct split |
104 |
Correct |
164 ms |
32736 KB |
ok, correct split |
105 |
Correct |
100 ms |
27092 KB |
ok, correct split |
106 |
Correct |
215 ms |
40256 KB |
ok, correct split |
107 |
Correct |
159 ms |
31568 KB |
ok, correct split |
108 |
Correct |
162 ms |
31292 KB |
ok, correct split |
109 |
Correct |
231 ms |
33384 KB |
ok, correct split |
110 |
Correct |
228 ms |
34360 KB |
ok, correct split |
111 |
Correct |
226 ms |
34048 KB |
ok, correct split |
112 |
Correct |
220 ms |
34732 KB |
ok, correct split |
113 |
Correct |
212 ms |
34368 KB |
ok, correct split |
114 |
Correct |
34 ms |
20856 KB |
ok, correct split |
115 |
Correct |
33 ms |
20600 KB |
ok, correct split |
116 |
Correct |
248 ms |
33880 KB |
ok, correct split |
117 |
Correct |
256 ms |
33288 KB |
ok, correct split |
118 |
Correct |
169 ms |
29932 KB |
ok, correct split |
119 |
Correct |
235 ms |
30344 KB |
ok, correct split |
120 |
Correct |
182 ms |
32504 KB |
ok, correct split |
121 |
Correct |
208 ms |
30072 KB |
ok, no valid answer |
122 |
Correct |
154 ms |
30704 KB |
ok, no valid answer |
123 |
Correct |
204 ms |
32088 KB |
ok, no valid answer |
124 |
Correct |
209 ms |
32376 KB |
ok, no valid answer |
125 |
Correct |
157 ms |
32752 KB |
ok, no valid answer |
126 |
Correct |
115 ms |
31904 KB |
ok, no valid answer |
127 |
Correct |
248 ms |
32356 KB |
ok, no valid answer |