#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int mx = 300000;
int sz[mx], sz2[mx];
bool explored[mx], explored2[mx], chosen[mx], A[mx], explored3[mx];
vector<int> mark(mx, 0), res, tbl(3);
vector<vector<int>> adj(mx), ch(mx), adj2(mx);
int n, cent, a, b, c, repA, repB;
bool valid;
void dfs(int u) {
explored[u] = true;
sz[u] = 1;
bool works = true;
for (int v: adj[u]) {
if (explored[v]) continue;
//cout << u << " " << v << "\n";
ch[u].push_back(v);
dfs(v);
if (sz[v] > n/2) works = false;
sz[u] += sz[v];
}
if (n - sz[u] > n/2) works = false;
if (works) cent = u;
}
void dfs2(int u) {
for (int v: ch[u]) {
//cout << v << "\n";
mark[v] = mark[u];
dfs2(v);
}
}
void dfs3(int u, vector<int>& comp) {
explored2[u] = true;
for (int v: adj2[u]) {
if (explored2[v]) continue;
comp.push_back(v);
dfs3(v, comp);
}
}
void dfs4(int u, int& cnt, bool inA) {
explored3[u] = true;
cnt++;
if (inA && cnt <= a) {
res[u] = tbl[0];
}
else if (!inA && cnt <= b) {
// cout << u << "\n";
res[u] = tbl[1];
}
for (int v: adj[u]) {
if (explored3[v] || A[v] != inA) continue;
dfs4(v, cnt, inA);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
::n = n;
vector<int> arr = {a,b,c};
tbl = {1,2,3};
sort(tbl.begin(),tbl.end(),[&arr](int i, int j){return arr[i-1] < arr[j-1];});
sort(arr.begin(),arr.end());
a = arr[0];
b = arr[1];
c = arr[2];
::a = a;
::b = b;
::c = c;
//cout << tbl[0] << " " << tbl[1] << " " << tbl[2] << "\n";
//assume a <= b <= c
for (int i = 0; i < (int)p.size(); i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs(2);
//cout << cent << "\n";
mark[cent] = -1;
sz2[0] = n - sz[cent];
for (int i = 0; i < (int)ch[cent].size(); i++) {
int u = ch[cent][i];
//cout << u << "\n";
mark[u] = i+1;
sz2[mark[u]] = sz[u];
dfs2(u);
}
//cout << mark[7] << "\n";
for (int i = 0; i < (int)p.size(); i++) {
if (p[i] == cent || q[i] == cent) continue;
// cout << p[i] << " " << q[i] << "\n";
if (mark[p[i]] != mark[q[i]]) {
adj2[mark[p[i]]].push_back(mark[q[i]]);
adj2[mark[q[i]]].push_back(mark[p[i]]);
//cout << mark[p[i]] << " " << mark[q[i]] << "\n";
}
}
for (int i = 0; i <= (int)ch[cent].size(); i++) {
vector<int> comp;
comp.push_back(i);
dfs3(i, comp);
int x = 0;
for (int c: comp) {
x += sz2[c];
}
//cout << x << "\n";
if (x >= a) {
sort(comp.begin(),comp.end(),[](int i, int j){return sz2[i] > sz2[j];});
while (x - sz2[comp.back()] >= a) {
x -= sz2[comp.back()];
comp.pop_back();
}
//cout << comp[0] << "\n";
for (int c: comp) chosen[c] = true;
for (int i = 0; i < n; i++) {
if (i == cent) continue;
A[i] = chosen[mark[i]];
if (A[i]) {
//cout << i << " ";
repA = i;
}
else repB = i;
}
//cout << "hooray\n";
valid = true;
break;
}
}
if (valid) {
res.assign(n,tbl[2]);
int cnt = 0;
//cout << repA << " " << repB << "\n";
dfs4(repA, cnt, true);
cnt = 0;
dfs4(repB, cnt, false);
}
if (!valid) {
res.assign(n,0);
}
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
22656 KB |
ok, correct split |
2 |
Correct |
18 ms |
22656 KB |
ok, correct split |
3 |
Correct |
18 ms |
22656 KB |
ok, correct split |
4 |
Correct |
18 ms |
22656 KB |
ok, correct split |
5 |
Correct |
25 ms |
22656 KB |
ok, correct split |
6 |
Correct |
18 ms |
22656 KB |
ok, correct split |
7 |
Correct |
199 ms |
39032 KB |
ok, correct split |
8 |
Correct |
154 ms |
40824 KB |
ok, correct split |
9 |
Correct |
157 ms |
40312 KB |
ok, correct split |
10 |
Correct |
160 ms |
40952 KB |
ok, correct split |
11 |
Correct |
146 ms |
40952 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
22708 KB |
ok, correct split |
2 |
Correct |
19 ms |
22656 KB |
ok, correct split |
3 |
Correct |
18 ms |
22656 KB |
ok, correct split |
4 |
Correct |
172 ms |
37760 KB |
ok, correct split |
5 |
Correct |
126 ms |
31736 KB |
ok, correct split |
6 |
Correct |
148 ms |
40952 KB |
ok, correct split |
7 |
Correct |
164 ms |
38260 KB |
ok, correct split |
8 |
Correct |
192 ms |
35432 KB |
ok, correct split |
9 |
Correct |
137 ms |
33144 KB |
ok, correct split |
10 |
Correct |
78 ms |
30832 KB |
ok, correct split |
11 |
Correct |
83 ms |
30960 KB |
ok, correct split |
12 |
Correct |
79 ms |
31344 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
22656 KB |
ok, correct split |
2 |
Correct |
127 ms |
30648 KB |
ok, correct split |
3 |
Correct |
49 ms |
25848 KB |
ok, correct split |
4 |
Correct |
18 ms |
22656 KB |
ok, correct split |
5 |
Correct |
156 ms |
35532 KB |
ok, correct split |
6 |
Correct |
153 ms |
34680 KB |
ok, correct split |
7 |
Correct |
150 ms |
35608 KB |
ok, correct split |
8 |
Correct |
133 ms |
35192 KB |
ok, correct split |
9 |
Correct |
133 ms |
34040 KB |
ok, correct split |
10 |
Correct |
45 ms |
25208 KB |
ok, no valid answer |
11 |
Correct |
53 ms |
26488 KB |
ok, no valid answer |
12 |
Correct |
98 ms |
30068 KB |
ok, no valid answer |
13 |
Correct |
110 ms |
30328 KB |
ok, no valid answer |
14 |
Correct |
79 ms |
30064 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
22656 KB |
ok, correct split |
2 |
Correct |
19 ms |
22656 KB |
ok, no valid answer |
3 |
Correct |
18 ms |
22656 KB |
ok, correct split |
4 |
Correct |
18 ms |
22656 KB |
ok, correct split |
5 |
Correct |
18 ms |
22656 KB |
ok, correct split |
6 |
Correct |
18 ms |
22656 KB |
ok, correct split |
7 |
Correct |
18 ms |
22656 KB |
ok, correct split |
8 |
Correct |
20 ms |
22688 KB |
ok, correct split |
9 |
Correct |
21 ms |
23040 KB |
ok, correct split |
10 |
Correct |
21 ms |
23040 KB |
ok, correct split |
11 |
Correct |
19 ms |
22748 KB |
ok, correct split |
12 |
Correct |
21 ms |
23040 KB |
ok, correct split |
13 |
Correct |
18 ms |
22656 KB |
ok, correct split |
14 |
Correct |
20 ms |
22656 KB |
ok, correct split |
15 |
Correct |
18 ms |
22656 KB |
ok, correct split |
16 |
Correct |
20 ms |
22784 KB |
ok, correct split |
17 |
Correct |
19 ms |
22656 KB |
ok, correct split |
18 |
Correct |
18 ms |
22656 KB |
ok, correct split |
19 |
Correct |
19 ms |
22656 KB |
ok, correct split |
20 |
Correct |
19 ms |
22784 KB |
ok, correct split |
21 |
Correct |
20 ms |
23040 KB |
ok, correct split |
22 |
Correct |
20 ms |
23040 KB |
ok, correct split |
23 |
Correct |
19 ms |
23040 KB |
ok, correct split |
24 |
Correct |
22 ms |
23040 KB |
ok, correct split |
25 |
Correct |
22 ms |
23040 KB |
ok, correct split |
26 |
Correct |
22 ms |
23040 KB |
ok, correct split |
27 |
Correct |
20 ms |
23040 KB |
ok, correct split |
28 |
Correct |
21 ms |
23040 KB |
ok, correct split |
29 |
Correct |
19 ms |
22656 KB |
ok, correct split |
30 |
Correct |
20 ms |
23040 KB |
ok, correct split |
31 |
Correct |
19 ms |
22784 KB |
ok, correct split |
32 |
Correct |
19 ms |
22656 KB |
ok, correct split |
33 |
Correct |
18 ms |
22656 KB |
ok, correct split |
34 |
Correct |
21 ms |
22912 KB |
ok, correct split |
35 |
Correct |
20 ms |
22912 KB |
ok, correct split |
36 |
Correct |
19 ms |
22912 KB |
ok, correct split |
37 |
Correct |
22 ms |
23040 KB |
ok, correct split |
38 |
Correct |
21 ms |
23040 KB |
ok, correct split |
39 |
Correct |
22 ms |
23040 KB |
ok, correct split |
40 |
Correct |
23 ms |
23040 KB |
ok, correct split |
41 |
Correct |
20 ms |
22784 KB |
ok, correct split |
42 |
Correct |
20 ms |
22784 KB |
ok, correct split |
43 |
Correct |
21 ms |
23040 KB |
ok, correct split |
44 |
Correct |
21 ms |
23040 KB |
ok, correct split |
45 |
Correct |
22 ms |
23040 KB |
ok, correct split |
46 |
Correct |
21 ms |
23040 KB |
ok, correct split |
47 |
Correct |
21 ms |
22912 KB |
ok, no valid answer |
48 |
Correct |
20 ms |
22912 KB |
ok, correct split |
49 |
Correct |
22 ms |
23040 KB |
ok, correct split |
50 |
Correct |
18 ms |
22656 KB |
ok, no valid answer |
51 |
Correct |
18 ms |
22656 KB |
ok, no valid answer |
52 |
Correct |
22 ms |
22904 KB |
ok, no valid answer |
53 |
Correct |
21 ms |
23040 KB |
ok, no valid answer |
54 |
Correct |
21 ms |
22912 KB |
ok, no valid answer |
55 |
Correct |
22 ms |
22912 KB |
ok, no valid answer |
56 |
Correct |
22 ms |
23040 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
22656 KB |
ok, correct split |
2 |
Correct |
18 ms |
22656 KB |
ok, correct split |
3 |
Correct |
18 ms |
22656 KB |
ok, correct split |
4 |
Correct |
18 ms |
22656 KB |
ok, correct split |
5 |
Correct |
25 ms |
22656 KB |
ok, correct split |
6 |
Correct |
18 ms |
22656 KB |
ok, correct split |
7 |
Correct |
199 ms |
39032 KB |
ok, correct split |
8 |
Correct |
154 ms |
40824 KB |
ok, correct split |
9 |
Correct |
157 ms |
40312 KB |
ok, correct split |
10 |
Correct |
160 ms |
40952 KB |
ok, correct split |
11 |
Correct |
146 ms |
40952 KB |
ok, correct split |
12 |
Correct |
20 ms |
22708 KB |
ok, correct split |
13 |
Correct |
19 ms |
22656 KB |
ok, correct split |
14 |
Correct |
18 ms |
22656 KB |
ok, correct split |
15 |
Correct |
172 ms |
37760 KB |
ok, correct split |
16 |
Correct |
126 ms |
31736 KB |
ok, correct split |
17 |
Correct |
148 ms |
40952 KB |
ok, correct split |
18 |
Correct |
164 ms |
38260 KB |
ok, correct split |
19 |
Correct |
192 ms |
35432 KB |
ok, correct split |
20 |
Correct |
137 ms |
33144 KB |
ok, correct split |
21 |
Correct |
78 ms |
30832 KB |
ok, correct split |
22 |
Correct |
83 ms |
30960 KB |
ok, correct split |
23 |
Correct |
79 ms |
31344 KB |
ok, correct split |
24 |
Correct |
19 ms |
22656 KB |
ok, correct split |
25 |
Correct |
127 ms |
30648 KB |
ok, correct split |
26 |
Correct |
49 ms |
25848 KB |
ok, correct split |
27 |
Correct |
18 ms |
22656 KB |
ok, correct split |
28 |
Correct |
156 ms |
35532 KB |
ok, correct split |
29 |
Correct |
153 ms |
34680 KB |
ok, correct split |
30 |
Correct |
150 ms |
35608 KB |
ok, correct split |
31 |
Correct |
133 ms |
35192 KB |
ok, correct split |
32 |
Correct |
133 ms |
34040 KB |
ok, correct split |
33 |
Correct |
45 ms |
25208 KB |
ok, no valid answer |
34 |
Correct |
53 ms |
26488 KB |
ok, no valid answer |
35 |
Correct |
98 ms |
30068 KB |
ok, no valid answer |
36 |
Correct |
110 ms |
30328 KB |
ok, no valid answer |
37 |
Correct |
79 ms |
30064 KB |
ok, no valid answer |
38 |
Correct |
18 ms |
22656 KB |
ok, correct split |
39 |
Correct |
19 ms |
22656 KB |
ok, no valid answer |
40 |
Correct |
18 ms |
22656 KB |
ok, correct split |
41 |
Correct |
18 ms |
22656 KB |
ok, correct split |
42 |
Correct |
18 ms |
22656 KB |
ok, correct split |
43 |
Correct |
18 ms |
22656 KB |
ok, correct split |
44 |
Correct |
18 ms |
22656 KB |
ok, correct split |
45 |
Correct |
20 ms |
22688 KB |
ok, correct split |
46 |
Correct |
21 ms |
23040 KB |
ok, correct split |
47 |
Correct |
21 ms |
23040 KB |
ok, correct split |
48 |
Correct |
19 ms |
22748 KB |
ok, correct split |
49 |
Correct |
21 ms |
23040 KB |
ok, correct split |
50 |
Correct |
18 ms |
22656 KB |
ok, correct split |
51 |
Correct |
20 ms |
22656 KB |
ok, correct split |
52 |
Correct |
18 ms |
22656 KB |
ok, correct split |
53 |
Correct |
20 ms |
22784 KB |
ok, correct split |
54 |
Correct |
19 ms |
22656 KB |
ok, correct split |
55 |
Correct |
18 ms |
22656 KB |
ok, correct split |
56 |
Correct |
19 ms |
22656 KB |
ok, correct split |
57 |
Correct |
19 ms |
22784 KB |
ok, correct split |
58 |
Correct |
20 ms |
23040 KB |
ok, correct split |
59 |
Correct |
20 ms |
23040 KB |
ok, correct split |
60 |
Correct |
19 ms |
23040 KB |
ok, correct split |
61 |
Correct |
22 ms |
23040 KB |
ok, correct split |
62 |
Correct |
22 ms |
23040 KB |
ok, correct split |
63 |
Correct |
22 ms |
23040 KB |
ok, correct split |
64 |
Correct |
20 ms |
23040 KB |
ok, correct split |
65 |
Correct |
21 ms |
23040 KB |
ok, correct split |
66 |
Correct |
19 ms |
22656 KB |
ok, correct split |
67 |
Correct |
20 ms |
23040 KB |
ok, correct split |
68 |
Correct |
19 ms |
22784 KB |
ok, correct split |
69 |
Correct |
19 ms |
22656 KB |
ok, correct split |
70 |
Correct |
18 ms |
22656 KB |
ok, correct split |
71 |
Correct |
21 ms |
22912 KB |
ok, correct split |
72 |
Correct |
20 ms |
22912 KB |
ok, correct split |
73 |
Correct |
19 ms |
22912 KB |
ok, correct split |
74 |
Correct |
22 ms |
23040 KB |
ok, correct split |
75 |
Correct |
21 ms |
23040 KB |
ok, correct split |
76 |
Correct |
22 ms |
23040 KB |
ok, correct split |
77 |
Correct |
23 ms |
23040 KB |
ok, correct split |
78 |
Correct |
20 ms |
22784 KB |
ok, correct split |
79 |
Correct |
20 ms |
22784 KB |
ok, correct split |
80 |
Correct |
21 ms |
23040 KB |
ok, correct split |
81 |
Correct |
21 ms |
23040 KB |
ok, correct split |
82 |
Correct |
22 ms |
23040 KB |
ok, correct split |
83 |
Correct |
21 ms |
23040 KB |
ok, correct split |
84 |
Correct |
21 ms |
22912 KB |
ok, no valid answer |
85 |
Correct |
20 ms |
22912 KB |
ok, correct split |
86 |
Correct |
22 ms |
23040 KB |
ok, correct split |
87 |
Correct |
18 ms |
22656 KB |
ok, no valid answer |
88 |
Correct |
18 ms |
22656 KB |
ok, no valid answer |
89 |
Correct |
22 ms |
22904 KB |
ok, no valid answer |
90 |
Correct |
21 ms |
23040 KB |
ok, no valid answer |
91 |
Correct |
21 ms |
22912 KB |
ok, no valid answer |
92 |
Correct |
22 ms |
22912 KB |
ok, no valid answer |
93 |
Correct |
22 ms |
23040 KB |
ok, no valid answer |
94 |
Correct |
134 ms |
35064 KB |
ok, correct split |
95 |
Correct |
196 ms |
40964 KB |
ok, correct split |
96 |
Correct |
202 ms |
39296 KB |
ok, correct split |
97 |
Correct |
48 ms |
26232 KB |
ok, correct split |
98 |
Correct |
53 ms |
26488 KB |
ok, correct split |
99 |
Correct |
80 ms |
28920 KB |
ok, correct split |
100 |
Correct |
175 ms |
36212 KB |
ok, correct split |
101 |
Correct |
157 ms |
34808 KB |
ok, correct split |
102 |
Correct |
140 ms |
34288 KB |
ok, correct split |
103 |
Correct |
138 ms |
34056 KB |
ok, correct split |
104 |
Correct |
123 ms |
34148 KB |
ok, correct split |
105 |
Correct |
74 ms |
28664 KB |
ok, correct split |
106 |
Correct |
155 ms |
38044 KB |
ok, correct split |
107 |
Correct |
119 ms |
31736 KB |
ok, correct split |
108 |
Correct |
117 ms |
31736 KB |
ok, correct split |
109 |
Correct |
166 ms |
35448 KB |
ok, correct split |
110 |
Correct |
172 ms |
37336 KB |
ok, correct split |
111 |
Correct |
188 ms |
37488 KB |
ok, correct split |
112 |
Correct |
170 ms |
36080 KB |
ok, correct split |
113 |
Correct |
160 ms |
35952 KB |
ok, correct split |
114 |
Correct |
31 ms |
24320 KB |
ok, correct split |
115 |
Correct |
29 ms |
24064 KB |
ok, correct split |
116 |
Correct |
167 ms |
37360 KB |
ok, correct split |
117 |
Correct |
183 ms |
37232 KB |
ok, correct split |
118 |
Correct |
120 ms |
33144 KB |
ok, correct split |
119 |
Correct |
127 ms |
33144 KB |
ok, correct split |
120 |
Correct |
135 ms |
37880 KB |
ok, correct split |
121 |
Correct |
109 ms |
31608 KB |
ok, no valid answer |
122 |
Correct |
110 ms |
31480 KB |
ok, no valid answer |
123 |
Correct |
173 ms |
36216 KB |
ok, no valid answer |
124 |
Correct |
168 ms |
35832 KB |
ok, no valid answer |
125 |
Correct |
120 ms |
32624 KB |
ok, no valid answer |
126 |
Correct |
78 ms |
30376 KB |
ok, no valid answer |
127 |
Correct |
123 ms |
33520 KB |
ok, no valid answer |