#include "split.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
vector < int > ret;
set < int > G[N];
int n, m, a, b, c, par[N], sz[N], Can, mark[N], sub[N];
vector < pii > Del, extra[N];
int pre(int v, int P)
{
int ret = v;
mark[v] = 1;
sub[v] = 1;
vector < int > del;
for(auto u : G[v])
{
if(u == P) continue;
if(mark[u])
{
del.push_back(u);
continue;
}
int nxt = pre(u, v);
if(sub[u] * 2 > n) ret = nxt;
sub[v] += sub[u];
}
for(auto x : del)
{
if(G[v].find(x) != G[v].end())
{
Del.push_back(Mp(x, v));
G[v].erase(x);
}
}
return ret;
}
void solve(int v, int P, int jad)
{
par[v] = jad;
sz[jad] ++;
for(auto u : G[v])
{
if(u == P) continue;
solve(u, v, jad);
}
}
set < pii > st;
int calc(int x)
{
if(x == a) return 1;
if(x == b) return 2;
return 3;
}
int get(int x)
{
return (x == par[x]? x : par[x] = get(par[x]));
}
int unify(int v, int u)
{
pii late = Mp(v, u);
v = get(v), u = get(u);
if(v == u) return 0;
sz[v] += sz[u];
par[u] = v;
if(SZ(extra[v]) < SZ(extra[u]))
{
extra[v].swap(extra[u]);
}
for(auto now : extra[u])
{
extra[v].push_back(now);
}
extra[u].clear();
extra[v].push_back(late);
return 1;
}
vector < int > find_split(int _n, int _a, int _b, int _c, vector < int > p, vector < int > q)
{
n = _n;
a = _a;
b = _b;
c = _c;
m = SZ(p);
for(int i = 0; i < m; i ++)
{
p[i] ++, q[i] ++;
G[p[i]].insert(q[i]);
G[q[i]].insert(p[i]);
}
int cen = pre(1, 0);
memset(mark, 0, sizeof mark);
pre(cen, 0);
for(auto u : G[cen])
{
solve(u, cen, u);
}
sz[cen] = 1;
par[cen] = cen;
int id = 0;
for(auto u : G[cen])
{
if(sub[u] > sub[id]) id = u;
}
int Mn = min({a, b, c});
ret.resize(n, 0);
assert(id != 0);
for(auto [x, y] : Del)
{
if(sz[id] >= Mn) break;
if(x == cen || y == cen) continue;
if(unify(x, y))
{
id = get(id);
if(sz[get(x)] > sz[id])
{
id = get(x);
}
}
}
if(sz[id] < Mn)
{
return ret;
}
for(int i = 1; i <= n; i ++)
{
if(get(i) == id)
{
if(G[i].find(cen) != G[i].end())
{
G[i].erase(cen);
G[cen].erase(i);
}
}
}
for(auto [x, y] : extra[id])
{
G[x].insert(y);
G[y].insert(x);
}
int col = calc(Mn);
for(int i = 1; i <= n; i ++)
{
if(i == cen) continue;
if(get(i) == id)
{
st.insert(Mp(SZ(G[i]), i));
ret[i - 1] = col;
}
}
while(SZ(st) > Mn)
{
int node = st.begin()->S;
assert(SZ(G[node]) <= 1);
st.erase(st.begin());
ret[node - 1] = 0;
for(auto u : G[node])
{
st.erase(Mp(SZ(G[u]), u));
G[u].erase(node);
st.insert(Mp(SZ(G[u]), u));
}
G[node].clear();
}
int Mn2 = a + b + c - Mn - max({a, b, c});
assert(Mn2 <= (n - sz[id]));
int col2 = -1;
if(a == Mn2 && col != 1) { col2 = 1; }
else if(b == Mn2 && col != 2) { col2 = 2; }
else if(c == Mn2 && col != 3) { col2 = 3; }
assert(col2 != -1);
st.clear();
for(int i = 1; i <= n; i ++)
{
if(get(i) != id)
{
st.insert(Mp(SZ(G[i]), i));
ret[i - 1] = col2;
}
}
assert(SZ(st) >= Mn2);
while(SZ(st) > Mn2)
{
int node = st.begin()->S;
st.erase(st.begin());
assert(SZ(G[node]) <= 1);
ret[node - 1] = 0;
for(auto u : G[node])
{
st.erase(Mp(SZ(G[u]), u));
G[u].erase(node);
st.insert(Mp(SZ(G[u]), u));
}
G[node].clear();
}
for(int i = 0; i < n; i ++)
{
if(ret[i] == 0)
{
ret[i] = 1 + 2 + 3 - col - col2;
}
}
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
74572 KB |
ok, correct split |
2 |
Correct |
37 ms |
74684 KB |
ok, correct split |
3 |
Correct |
39 ms |
74672 KB |
ok, correct split |
4 |
Correct |
38 ms |
74612 KB |
ok, correct split |
5 |
Correct |
37 ms |
74628 KB |
ok, correct split |
6 |
Correct |
37 ms |
74716 KB |
ok, correct split |
7 |
Correct |
221 ms |
101464 KB |
ok, correct split |
8 |
Correct |
270 ms |
97492 KB |
ok, correct split |
9 |
Correct |
234 ms |
96716 KB |
ok, correct split |
10 |
Correct |
275 ms |
101632 KB |
ok, correct split |
11 |
Correct |
225 ms |
102124 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
74580 KB |
ok, correct split |
2 |
Correct |
38 ms |
74672 KB |
ok, correct split |
3 |
Correct |
44 ms |
74572 KB |
ok, correct split |
4 |
Correct |
377 ms |
98872 KB |
ok, correct split |
5 |
Correct |
243 ms |
91216 KB |
ok, correct split |
6 |
Correct |
257 ms |
101608 KB |
ok, correct split |
7 |
Correct |
234 ms |
97496 KB |
ok, correct split |
8 |
Correct |
406 ms |
99036 KB |
ok, correct split |
9 |
Correct |
230 ms |
89080 KB |
ok, correct split |
10 |
Correct |
205 ms |
92296 KB |
ok, correct split |
11 |
Correct |
223 ms |
92224 KB |
ok, correct split |
12 |
Correct |
217 ms |
92272 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
74668 KB |
ok, correct split |
2 |
Correct |
214 ms |
90744 KB |
ok, correct split |
3 |
Correct |
95 ms |
81280 KB |
ok, correct split |
4 |
Correct |
41 ms |
74576 KB |
ok, correct split |
5 |
Correct |
241 ms |
94652 KB |
ok, correct split |
6 |
Correct |
223 ms |
94412 KB |
ok, correct split |
7 |
Correct |
227 ms |
94180 KB |
ok, correct split |
8 |
Correct |
231 ms |
96204 KB |
ok, correct split |
9 |
Correct |
221 ms |
94156 KB |
ok, correct split |
10 |
Correct |
68 ms |
78980 KB |
ok, no valid answer |
11 |
Correct |
85 ms |
81136 KB |
ok, no valid answer |
12 |
Correct |
150 ms |
87552 KB |
ok, no valid answer |
13 |
Correct |
150 ms |
87528 KB |
ok, no valid answer |
14 |
Correct |
198 ms |
87480 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
74624 KB |
ok, correct split |
2 |
Correct |
37 ms |
74580 KB |
ok, no valid answer |
3 |
Correct |
37 ms |
74572 KB |
ok, correct split |
4 |
Correct |
37 ms |
74560 KB |
ok, correct split |
5 |
Correct |
39 ms |
74708 KB |
ok, correct split |
6 |
Correct |
42 ms |
74572 KB |
ok, correct split |
7 |
Correct |
36 ms |
74584 KB |
ok, correct split |
8 |
Correct |
35 ms |
74580 KB |
ok, correct split |
9 |
Correct |
39 ms |
75404 KB |
ok, correct split |
10 |
Correct |
41 ms |
75244 KB |
ok, correct split |
11 |
Correct |
36 ms |
74720 KB |
ok, correct split |
12 |
Correct |
39 ms |
75332 KB |
ok, correct split |
13 |
Correct |
37 ms |
74616 KB |
ok, correct split |
14 |
Correct |
36 ms |
74572 KB |
ok, correct split |
15 |
Correct |
45 ms |
74600 KB |
ok, correct split |
16 |
Correct |
35 ms |
74580 KB |
ok, correct split |
17 |
Correct |
36 ms |
74640 KB |
ok, correct split |
18 |
Correct |
50 ms |
74612 KB |
ok, correct split |
19 |
Correct |
43 ms |
74748 KB |
ok, correct split |
20 |
Correct |
38 ms |
74920 KB |
ok, correct split |
21 |
Correct |
38 ms |
75048 KB |
ok, correct split |
22 |
Correct |
51 ms |
75076 KB |
ok, correct split |
23 |
Correct |
39 ms |
75136 KB |
ok, correct split |
24 |
Correct |
37 ms |
75136 KB |
ok, correct split |
25 |
Correct |
37 ms |
75084 KB |
ok, correct split |
26 |
Correct |
40 ms |
75292 KB |
ok, correct split |
27 |
Correct |
45 ms |
75228 KB |
ok, correct split |
28 |
Correct |
39 ms |
75288 KB |
ok, correct split |
29 |
Correct |
36 ms |
74684 KB |
ok, correct split |
30 |
Correct |
40 ms |
75232 KB |
ok, correct split |
31 |
Correct |
36 ms |
74836 KB |
ok, correct split |
32 |
Correct |
35 ms |
74648 KB |
ok, correct split |
33 |
Correct |
39 ms |
74640 KB |
ok, correct split |
34 |
Correct |
41 ms |
75028 KB |
ok, correct split |
35 |
Correct |
40 ms |
75048 KB |
ok, correct split |
36 |
Correct |
36 ms |
74984 KB |
ok, correct split |
37 |
Correct |
39 ms |
75256 KB |
ok, correct split |
38 |
Correct |
43 ms |
75364 KB |
ok, correct split |
39 |
Correct |
50 ms |
75348 KB |
ok, correct split |
40 |
Correct |
42 ms |
75340 KB |
ok, correct split |
41 |
Correct |
38 ms |
74992 KB |
ok, correct split |
42 |
Correct |
39 ms |
74956 KB |
ok, correct split |
43 |
Correct |
47 ms |
75344 KB |
ok, correct split |
44 |
Correct |
45 ms |
75336 KB |
ok, correct split |
45 |
Correct |
42 ms |
75212 KB |
ok, correct split |
46 |
Correct |
41 ms |
75056 KB |
ok, correct split |
47 |
Correct |
42 ms |
74976 KB |
ok, no valid answer |
48 |
Correct |
39 ms |
75032 KB |
ok, correct split |
49 |
Correct |
37 ms |
75188 KB |
ok, correct split |
50 |
Correct |
38 ms |
74636 KB |
ok, no valid answer |
51 |
Correct |
36 ms |
74684 KB |
ok, no valid answer |
52 |
Correct |
37 ms |
74860 KB |
ok, no valid answer |
53 |
Correct |
42 ms |
75336 KB |
ok, no valid answer |
54 |
Correct |
45 ms |
74924 KB |
ok, no valid answer |
55 |
Correct |
44 ms |
75168 KB |
ok, no valid answer |
56 |
Correct |
42 ms |
75048 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
74572 KB |
ok, correct split |
2 |
Correct |
37 ms |
74684 KB |
ok, correct split |
3 |
Correct |
39 ms |
74672 KB |
ok, correct split |
4 |
Correct |
38 ms |
74612 KB |
ok, correct split |
5 |
Correct |
37 ms |
74628 KB |
ok, correct split |
6 |
Correct |
37 ms |
74716 KB |
ok, correct split |
7 |
Correct |
221 ms |
101464 KB |
ok, correct split |
8 |
Correct |
270 ms |
97492 KB |
ok, correct split |
9 |
Correct |
234 ms |
96716 KB |
ok, correct split |
10 |
Correct |
275 ms |
101632 KB |
ok, correct split |
11 |
Correct |
225 ms |
102124 KB |
ok, correct split |
12 |
Correct |
35 ms |
74580 KB |
ok, correct split |
13 |
Correct |
38 ms |
74672 KB |
ok, correct split |
14 |
Correct |
44 ms |
74572 KB |
ok, correct split |
15 |
Correct |
377 ms |
98872 KB |
ok, correct split |
16 |
Correct |
243 ms |
91216 KB |
ok, correct split |
17 |
Correct |
257 ms |
101608 KB |
ok, correct split |
18 |
Correct |
234 ms |
97496 KB |
ok, correct split |
19 |
Correct |
406 ms |
99036 KB |
ok, correct split |
20 |
Correct |
230 ms |
89080 KB |
ok, correct split |
21 |
Correct |
205 ms |
92296 KB |
ok, correct split |
22 |
Correct |
223 ms |
92224 KB |
ok, correct split |
23 |
Correct |
217 ms |
92272 KB |
ok, correct split |
24 |
Correct |
38 ms |
74668 KB |
ok, correct split |
25 |
Correct |
214 ms |
90744 KB |
ok, correct split |
26 |
Correct |
95 ms |
81280 KB |
ok, correct split |
27 |
Correct |
41 ms |
74576 KB |
ok, correct split |
28 |
Correct |
241 ms |
94652 KB |
ok, correct split |
29 |
Correct |
223 ms |
94412 KB |
ok, correct split |
30 |
Correct |
227 ms |
94180 KB |
ok, correct split |
31 |
Correct |
231 ms |
96204 KB |
ok, correct split |
32 |
Correct |
221 ms |
94156 KB |
ok, correct split |
33 |
Correct |
68 ms |
78980 KB |
ok, no valid answer |
34 |
Correct |
85 ms |
81136 KB |
ok, no valid answer |
35 |
Correct |
150 ms |
87552 KB |
ok, no valid answer |
36 |
Correct |
150 ms |
87528 KB |
ok, no valid answer |
37 |
Correct |
198 ms |
87480 KB |
ok, no valid answer |
38 |
Correct |
37 ms |
74624 KB |
ok, correct split |
39 |
Correct |
37 ms |
74580 KB |
ok, no valid answer |
40 |
Correct |
37 ms |
74572 KB |
ok, correct split |
41 |
Correct |
37 ms |
74560 KB |
ok, correct split |
42 |
Correct |
39 ms |
74708 KB |
ok, correct split |
43 |
Correct |
42 ms |
74572 KB |
ok, correct split |
44 |
Correct |
36 ms |
74584 KB |
ok, correct split |
45 |
Correct |
35 ms |
74580 KB |
ok, correct split |
46 |
Correct |
39 ms |
75404 KB |
ok, correct split |
47 |
Correct |
41 ms |
75244 KB |
ok, correct split |
48 |
Correct |
36 ms |
74720 KB |
ok, correct split |
49 |
Correct |
39 ms |
75332 KB |
ok, correct split |
50 |
Correct |
37 ms |
74616 KB |
ok, correct split |
51 |
Correct |
36 ms |
74572 KB |
ok, correct split |
52 |
Correct |
45 ms |
74600 KB |
ok, correct split |
53 |
Correct |
35 ms |
74580 KB |
ok, correct split |
54 |
Correct |
36 ms |
74640 KB |
ok, correct split |
55 |
Correct |
50 ms |
74612 KB |
ok, correct split |
56 |
Correct |
43 ms |
74748 KB |
ok, correct split |
57 |
Correct |
38 ms |
74920 KB |
ok, correct split |
58 |
Correct |
38 ms |
75048 KB |
ok, correct split |
59 |
Correct |
51 ms |
75076 KB |
ok, correct split |
60 |
Correct |
39 ms |
75136 KB |
ok, correct split |
61 |
Correct |
37 ms |
75136 KB |
ok, correct split |
62 |
Correct |
37 ms |
75084 KB |
ok, correct split |
63 |
Correct |
40 ms |
75292 KB |
ok, correct split |
64 |
Correct |
45 ms |
75228 KB |
ok, correct split |
65 |
Correct |
39 ms |
75288 KB |
ok, correct split |
66 |
Correct |
36 ms |
74684 KB |
ok, correct split |
67 |
Correct |
40 ms |
75232 KB |
ok, correct split |
68 |
Correct |
36 ms |
74836 KB |
ok, correct split |
69 |
Correct |
35 ms |
74648 KB |
ok, correct split |
70 |
Correct |
39 ms |
74640 KB |
ok, correct split |
71 |
Correct |
41 ms |
75028 KB |
ok, correct split |
72 |
Correct |
40 ms |
75048 KB |
ok, correct split |
73 |
Correct |
36 ms |
74984 KB |
ok, correct split |
74 |
Correct |
39 ms |
75256 KB |
ok, correct split |
75 |
Correct |
43 ms |
75364 KB |
ok, correct split |
76 |
Correct |
50 ms |
75348 KB |
ok, correct split |
77 |
Correct |
42 ms |
75340 KB |
ok, correct split |
78 |
Correct |
38 ms |
74992 KB |
ok, correct split |
79 |
Correct |
39 ms |
74956 KB |
ok, correct split |
80 |
Correct |
47 ms |
75344 KB |
ok, correct split |
81 |
Correct |
45 ms |
75336 KB |
ok, correct split |
82 |
Correct |
42 ms |
75212 KB |
ok, correct split |
83 |
Correct |
41 ms |
75056 KB |
ok, correct split |
84 |
Correct |
42 ms |
74976 KB |
ok, no valid answer |
85 |
Correct |
39 ms |
75032 KB |
ok, correct split |
86 |
Correct |
37 ms |
75188 KB |
ok, correct split |
87 |
Correct |
38 ms |
74636 KB |
ok, no valid answer |
88 |
Correct |
36 ms |
74684 KB |
ok, no valid answer |
89 |
Correct |
37 ms |
74860 KB |
ok, no valid answer |
90 |
Correct |
42 ms |
75336 KB |
ok, no valid answer |
91 |
Correct |
45 ms |
74924 KB |
ok, no valid answer |
92 |
Correct |
44 ms |
75168 KB |
ok, no valid answer |
93 |
Correct |
42 ms |
75048 KB |
ok, no valid answer |
94 |
Correct |
315 ms |
95180 KB |
ok, correct split |
95 |
Correct |
483 ms |
109808 KB |
ok, correct split |
96 |
Correct |
371 ms |
104756 KB |
ok, correct split |
97 |
Correct |
89 ms |
82080 KB |
ok, correct split |
98 |
Correct |
190 ms |
82084 KB |
ok, correct split |
99 |
Correct |
160 ms |
89788 KB |
ok, correct split |
100 |
Correct |
445 ms |
102824 KB |
ok, correct split |
101 |
Correct |
385 ms |
98632 KB |
ok, correct split |
102 |
Correct |
392 ms |
98244 KB |
ok, correct split |
103 |
Correct |
379 ms |
96908 KB |
ok, correct split |
104 |
Correct |
372 ms |
101952 KB |
ok, correct split |
105 |
Correct |
137 ms |
85160 KB |
ok, correct split |
106 |
Correct |
463 ms |
102756 KB |
ok, correct split |
107 |
Correct |
235 ms |
91856 KB |
ok, correct split |
108 |
Correct |
225 ms |
91600 KB |
ok, correct split |
109 |
Correct |
431 ms |
101184 KB |
ok, correct split |
110 |
Correct |
433 ms |
102460 KB |
ok, correct split |
111 |
Correct |
482 ms |
102496 KB |
ok, correct split |
112 |
Correct |
484 ms |
102220 KB |
ok, correct split |
113 |
Correct |
484 ms |
102424 KB |
ok, correct split |
114 |
Correct |
65 ms |
78316 KB |
ok, correct split |
115 |
Correct |
55 ms |
77620 KB |
ok, correct split |
116 |
Correct |
478 ms |
102412 KB |
ok, correct split |
117 |
Correct |
535 ms |
101880 KB |
ok, correct split |
118 |
Correct |
228 ms |
90692 KB |
ok, correct split |
119 |
Correct |
242 ms |
93340 KB |
ok, correct split |
120 |
Correct |
242 ms |
98172 KB |
ok, correct split |
121 |
Correct |
189 ms |
89104 KB |
ok, no valid answer |
122 |
Correct |
162 ms |
88692 KB |
ok, no valid answer |
123 |
Correct |
378 ms |
102932 KB |
ok, no valid answer |
124 |
Correct |
356 ms |
102808 KB |
ok, no valid answer |
125 |
Correct |
235 ms |
93124 KB |
ok, no valid answer |
126 |
Correct |
141 ms |
87440 KB |
ok, no valid answer |
127 |
Correct |
276 ms |
95648 KB |
ok, no valid answer |