#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
const int nax=2e5+5;
int n;
int a, b, c;
int ord[4];
vi graf[nax];
vi tree[nax];
int sz[nax];
int komp[nax];
void dfs_sz(int u, int p)
{
sz[u]=1;
for (int v:tree[u])
{
if (v==p) continue;
dfs_sz(v, u);
sz[u]+=sz[v];
}
}
int dfsf(int u, int p)
{
for (int v:tree[u])
{
if (v==p) continue;
if (sz[v]*2>=n)
return dfsf(v, u);
}
return u;
}
int centroid()
{
dfs_sz(0, 0);
return dfsf(0, 0);
}
void dfs_down(int u, int p, vi& ans)
{
if (a==0) return;
a--;
//assert(ans[u]==0);
ans[u]=ord[1];
for (int v:tree[u])
{
if (v==p) continue;
dfs_down(v, u, ans);
}
}
void dfs_fill2(int u, int p, vi& ans)
{
if (b==0) return;
b--;
assert(ans[u]==0);
ans[u]=ord[2];
for (int v:tree[u])
{
if (v==p||ans[v]!=0) continue;
dfs_fill2(v, u, ans);
}
}
bool was[nax];
void dfs_tree(int u, int p)
{
was[u]=true;
for (int v:graf[u])
{
if (was[v]) continue;
tree[u].push_back(v);
tree[v].push_back(u);
dfs_tree(v, u);
}
}
void dfs_par(int u, int p, int c)
{
komp[u] = c;
for (int v:tree[u])
{
if (v==p) continue;
dfs_par(v, u, c);
}
}
vi ct[nax];
vi ls;
int vis[nax];
int tot;
void dfs_fin(int u)
{
ls.push_back(u);
vis[u]=1;
tot+=sz[u];
if (tot>=a) return;
for (int v:ct[u])
{
if (!vis[v]) dfs_fin(v);
if (tot>=a) return;
}
}
vi find_split(int N, int A, int B, int C, vi u, vi v)
{
n=N; a=A; b=B; c=C;
ord[1]=1;
ord[2]=2;
ord[3]=3;
if (a>c)
{
swap(a,c);
swap(ord[1],ord[3]);
}
if (b>c)
{
swap(b,c);
swap(ord[2],ord[3]);
}
if (a>b)
{
swap(a,b);
swap(ord[1],ord[2]);
}
int m=v.size();
for (int i=0; i<m; i++)
{
graf[u[i]].push_back(v[i]);
graf[v[i]].push_back(u[i]);
}
if (m==n-1)
{
for (int i=0;i<m;i++)
{
tree[u[i]].push_back(v[i]);
tree[v[i]].push_back(u[i]);
}
C=c;
int c=centroid();
dfs_sz(c, c);
for(int v:graf[c])
{
if (sz[v]>=a)
{
vi ans(n);
dfs_down(v, c, ans);
//assert(sz[c]-sz[v]>=b);
dfs_fill2(c, v, ans);
for (int i=0; i<n; i++)
{
if (ans[i]==0)
{
C--;
ans[i]=ord[3];
}
}
return ans;
}
}
vi ans(n);
return ans;
}
dfs_tree(0, 0);
int cen=centroid();
dfs_sz(cen, cen);
for (int v:tree[cen])
{
if (sz[v]>=a)
{
vi ans(n);
dfs_down(v, cen, ans);
dfs_fill2(cen, v, ans);
for (int i=0; i<n; i++)
{
if (ans[i]==0)
{
ans[i]=ord[3];
}
}
return ans;
}
}
for (int v:tree[cen])
{
dfs_par(v,cen,v);
}
for (int i=0; i<m; i++)
{
if (u[i]!=cen && v[i]!=cen && komp[u[i]] != komp[v[i]])
{
ct[komp[u[i]]].push_back(komp[v[i]]);
ct[komp[v[i]]].push_back(komp[u[i]]);
}
}
for (int v:tree[cen])
{
if (!vis[v])
{
ls.clear();
tot=0;
dfs_fin(v);
if (tot>=a)
{
vi ans(n);
for (int who:ls)
{
dfs_down(who, cen, ans);
}
bool ok=false;
for (int i=0; i<n; i++)
if (ans[i]==ord[1])
ok=true;
assert(ok);
dfs_fill2(cen, cen, ans);
for (int i=0; i<n; i++)
{
if (ans[i]==0)
{
ans[i]=ord[3];
}
}
return ans;
}
}
}
vi ans(n);
return ans;
}
/*
9 10
4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14284 KB |
ok, correct split |
2 |
Correct |
7 ms |
14388 KB |
ok, correct split |
3 |
Correct |
7 ms |
14284 KB |
ok, correct split |
4 |
Correct |
7 ms |
14284 KB |
ok, correct split |
5 |
Correct |
10 ms |
14404 KB |
ok, correct split |
6 |
Correct |
7 ms |
14412 KB |
ok, correct split |
7 |
Correct |
92 ms |
30420 KB |
ok, correct split |
8 |
Correct |
85 ms |
28116 KB |
ok, correct split |
9 |
Correct |
100 ms |
27476 KB |
ok, correct split |
10 |
Correct |
86 ms |
30912 KB |
ok, correct split |
11 |
Correct |
95 ms |
30924 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14284 KB |
ok, correct split |
2 |
Correct |
7 ms |
14284 KB |
ok, correct split |
3 |
Correct |
8 ms |
14412 KB |
ok, correct split |
4 |
Correct |
105 ms |
27720 KB |
ok, correct split |
5 |
Correct |
77 ms |
23112 KB |
ok, correct split |
6 |
Correct |
89 ms |
30936 KB |
ok, correct split |
7 |
Correct |
90 ms |
27952 KB |
ok, correct split |
8 |
Correct |
105 ms |
25028 KB |
ok, correct split |
9 |
Correct |
94 ms |
23108 KB |
ok, correct split |
10 |
Correct |
55 ms |
23760 KB |
ok, correct split |
11 |
Correct |
59 ms |
23752 KB |
ok, correct split |
12 |
Correct |
56 ms |
23792 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14284 KB |
ok, correct split |
2 |
Correct |
75 ms |
23120 KB |
ok, correct split |
3 |
Correct |
31 ms |
17860 KB |
ok, correct split |
4 |
Correct |
8 ms |
14284 KB |
ok, correct split |
5 |
Correct |
87 ms |
25540 KB |
ok, correct split |
6 |
Correct |
84 ms |
25236 KB |
ok, correct split |
7 |
Correct |
82 ms |
25296 KB |
ok, correct split |
8 |
Correct |
97 ms |
26492 KB |
ok, correct split |
9 |
Correct |
84 ms |
25288 KB |
ok, correct split |
10 |
Correct |
26 ms |
17332 KB |
ok, no valid answer |
11 |
Correct |
36 ms |
18760 KB |
ok, no valid answer |
12 |
Correct |
60 ms |
23488 KB |
ok, no valid answer |
13 |
Correct |
75 ms |
23280 KB |
ok, no valid answer |
14 |
Correct |
57 ms |
23740 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14284 KB |
ok, correct split |
2 |
Correct |
7 ms |
14284 KB |
ok, no valid answer |
3 |
Correct |
7 ms |
14328 KB |
ok, correct split |
4 |
Correct |
7 ms |
14284 KB |
ok, correct split |
5 |
Correct |
8 ms |
14372 KB |
ok, correct split |
6 |
Correct |
7 ms |
14292 KB |
ok, correct split |
7 |
Correct |
7 ms |
14284 KB |
ok, correct split |
8 |
Correct |
7 ms |
14284 KB |
ok, correct split |
9 |
Correct |
9 ms |
14668 KB |
ok, correct split |
10 |
Correct |
10 ms |
14668 KB |
ok, correct split |
11 |
Correct |
8 ms |
14412 KB |
ok, correct split |
12 |
Correct |
9 ms |
14668 KB |
ok, correct split |
13 |
Correct |
7 ms |
14284 KB |
ok, correct split |
14 |
Correct |
8 ms |
14284 KB |
ok, correct split |
15 |
Correct |
7 ms |
14284 KB |
ok, correct split |
16 |
Correct |
7 ms |
14284 KB |
ok, correct split |
17 |
Correct |
7 ms |
14284 KB |
ok, correct split |
18 |
Correct |
7 ms |
14408 KB |
ok, correct split |
19 |
Correct |
7 ms |
14412 KB |
ok, correct split |
20 |
Correct |
8 ms |
14412 KB |
ok, correct split |
21 |
Correct |
9 ms |
14604 KB |
ok, correct split |
22 |
Correct |
9 ms |
14668 KB |
ok, correct split |
23 |
Correct |
9 ms |
14704 KB |
ok, correct split |
24 |
Correct |
8 ms |
14668 KB |
ok, correct split |
25 |
Correct |
9 ms |
14668 KB |
ok, correct split |
26 |
Correct |
9 ms |
14736 KB |
ok, correct split |
27 |
Correct |
9 ms |
14784 KB |
ok, correct split |
28 |
Correct |
9 ms |
14708 KB |
ok, correct split |
29 |
Correct |
8 ms |
14404 KB |
ok, correct split |
30 |
Correct |
9 ms |
14656 KB |
ok, correct split |
31 |
Correct |
8 ms |
14412 KB |
ok, correct split |
32 |
Correct |
8 ms |
14396 KB |
ok, correct split |
33 |
Correct |
8 ms |
14412 KB |
ok, correct split |
34 |
Correct |
11 ms |
14668 KB |
ok, correct split |
35 |
Correct |
9 ms |
14680 KB |
ok, correct split |
36 |
Correct |
11 ms |
14580 KB |
ok, correct split |
37 |
Correct |
9 ms |
14668 KB |
ok, correct split |
38 |
Correct |
9 ms |
14732 KB |
ok, correct split |
39 |
Correct |
9 ms |
14668 KB |
ok, correct split |
40 |
Correct |
9 ms |
14668 KB |
ok, correct split |
41 |
Correct |
8 ms |
14540 KB |
ok, correct split |
42 |
Correct |
8 ms |
14540 KB |
ok, correct split |
43 |
Correct |
10 ms |
14796 KB |
ok, correct split |
44 |
Correct |
9 ms |
14668 KB |
ok, correct split |
45 |
Correct |
11 ms |
14668 KB |
ok, correct split |
46 |
Correct |
9 ms |
14664 KB |
ok, correct split |
47 |
Correct |
10 ms |
14668 KB |
ok, no valid answer |
48 |
Correct |
8 ms |
14548 KB |
ok, correct split |
49 |
Correct |
9 ms |
14668 KB |
ok, correct split |
50 |
Correct |
7 ms |
14412 KB |
ok, no valid answer |
51 |
Correct |
7 ms |
14284 KB |
ok, no valid answer |
52 |
Correct |
9 ms |
14668 KB |
ok, no valid answer |
53 |
Correct |
9 ms |
14672 KB |
ok, no valid answer |
54 |
Correct |
9 ms |
14668 KB |
ok, no valid answer |
55 |
Correct |
11 ms |
14668 KB |
ok, no valid answer |
56 |
Correct |
9 ms |
14668 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14284 KB |
ok, correct split |
2 |
Correct |
7 ms |
14388 KB |
ok, correct split |
3 |
Correct |
7 ms |
14284 KB |
ok, correct split |
4 |
Correct |
7 ms |
14284 KB |
ok, correct split |
5 |
Correct |
10 ms |
14404 KB |
ok, correct split |
6 |
Correct |
7 ms |
14412 KB |
ok, correct split |
7 |
Correct |
92 ms |
30420 KB |
ok, correct split |
8 |
Correct |
85 ms |
28116 KB |
ok, correct split |
9 |
Correct |
100 ms |
27476 KB |
ok, correct split |
10 |
Correct |
86 ms |
30912 KB |
ok, correct split |
11 |
Correct |
95 ms |
30924 KB |
ok, correct split |
12 |
Correct |
7 ms |
14284 KB |
ok, correct split |
13 |
Correct |
7 ms |
14284 KB |
ok, correct split |
14 |
Correct |
8 ms |
14412 KB |
ok, correct split |
15 |
Correct |
105 ms |
27720 KB |
ok, correct split |
16 |
Correct |
77 ms |
23112 KB |
ok, correct split |
17 |
Correct |
89 ms |
30936 KB |
ok, correct split |
18 |
Correct |
90 ms |
27952 KB |
ok, correct split |
19 |
Correct |
105 ms |
25028 KB |
ok, correct split |
20 |
Correct |
94 ms |
23108 KB |
ok, correct split |
21 |
Correct |
55 ms |
23760 KB |
ok, correct split |
22 |
Correct |
59 ms |
23752 KB |
ok, correct split |
23 |
Correct |
56 ms |
23792 KB |
ok, correct split |
24 |
Correct |
7 ms |
14284 KB |
ok, correct split |
25 |
Correct |
75 ms |
23120 KB |
ok, correct split |
26 |
Correct |
31 ms |
17860 KB |
ok, correct split |
27 |
Correct |
8 ms |
14284 KB |
ok, correct split |
28 |
Correct |
87 ms |
25540 KB |
ok, correct split |
29 |
Correct |
84 ms |
25236 KB |
ok, correct split |
30 |
Correct |
82 ms |
25296 KB |
ok, correct split |
31 |
Correct |
97 ms |
26492 KB |
ok, correct split |
32 |
Correct |
84 ms |
25288 KB |
ok, correct split |
33 |
Correct |
26 ms |
17332 KB |
ok, no valid answer |
34 |
Correct |
36 ms |
18760 KB |
ok, no valid answer |
35 |
Correct |
60 ms |
23488 KB |
ok, no valid answer |
36 |
Correct |
75 ms |
23280 KB |
ok, no valid answer |
37 |
Correct |
57 ms |
23740 KB |
ok, no valid answer |
38 |
Correct |
7 ms |
14284 KB |
ok, correct split |
39 |
Correct |
7 ms |
14284 KB |
ok, no valid answer |
40 |
Correct |
7 ms |
14328 KB |
ok, correct split |
41 |
Correct |
7 ms |
14284 KB |
ok, correct split |
42 |
Correct |
8 ms |
14372 KB |
ok, correct split |
43 |
Correct |
7 ms |
14292 KB |
ok, correct split |
44 |
Correct |
7 ms |
14284 KB |
ok, correct split |
45 |
Correct |
7 ms |
14284 KB |
ok, correct split |
46 |
Correct |
9 ms |
14668 KB |
ok, correct split |
47 |
Correct |
10 ms |
14668 KB |
ok, correct split |
48 |
Correct |
8 ms |
14412 KB |
ok, correct split |
49 |
Correct |
9 ms |
14668 KB |
ok, correct split |
50 |
Correct |
7 ms |
14284 KB |
ok, correct split |
51 |
Correct |
8 ms |
14284 KB |
ok, correct split |
52 |
Correct |
7 ms |
14284 KB |
ok, correct split |
53 |
Correct |
7 ms |
14284 KB |
ok, correct split |
54 |
Correct |
7 ms |
14284 KB |
ok, correct split |
55 |
Correct |
7 ms |
14408 KB |
ok, correct split |
56 |
Correct |
7 ms |
14412 KB |
ok, correct split |
57 |
Correct |
8 ms |
14412 KB |
ok, correct split |
58 |
Correct |
9 ms |
14604 KB |
ok, correct split |
59 |
Correct |
9 ms |
14668 KB |
ok, correct split |
60 |
Correct |
9 ms |
14704 KB |
ok, correct split |
61 |
Correct |
8 ms |
14668 KB |
ok, correct split |
62 |
Correct |
9 ms |
14668 KB |
ok, correct split |
63 |
Correct |
9 ms |
14736 KB |
ok, correct split |
64 |
Correct |
9 ms |
14784 KB |
ok, correct split |
65 |
Correct |
9 ms |
14708 KB |
ok, correct split |
66 |
Correct |
8 ms |
14404 KB |
ok, correct split |
67 |
Correct |
9 ms |
14656 KB |
ok, correct split |
68 |
Correct |
8 ms |
14412 KB |
ok, correct split |
69 |
Correct |
8 ms |
14396 KB |
ok, correct split |
70 |
Correct |
8 ms |
14412 KB |
ok, correct split |
71 |
Correct |
11 ms |
14668 KB |
ok, correct split |
72 |
Correct |
9 ms |
14680 KB |
ok, correct split |
73 |
Correct |
11 ms |
14580 KB |
ok, correct split |
74 |
Correct |
9 ms |
14668 KB |
ok, correct split |
75 |
Correct |
9 ms |
14732 KB |
ok, correct split |
76 |
Correct |
9 ms |
14668 KB |
ok, correct split |
77 |
Correct |
9 ms |
14668 KB |
ok, correct split |
78 |
Correct |
8 ms |
14540 KB |
ok, correct split |
79 |
Correct |
8 ms |
14540 KB |
ok, correct split |
80 |
Correct |
10 ms |
14796 KB |
ok, correct split |
81 |
Correct |
9 ms |
14668 KB |
ok, correct split |
82 |
Correct |
11 ms |
14668 KB |
ok, correct split |
83 |
Correct |
9 ms |
14664 KB |
ok, correct split |
84 |
Correct |
10 ms |
14668 KB |
ok, no valid answer |
85 |
Correct |
8 ms |
14548 KB |
ok, correct split |
86 |
Correct |
9 ms |
14668 KB |
ok, correct split |
87 |
Correct |
7 ms |
14412 KB |
ok, no valid answer |
88 |
Correct |
7 ms |
14284 KB |
ok, no valid answer |
89 |
Correct |
9 ms |
14668 KB |
ok, no valid answer |
90 |
Correct |
9 ms |
14672 KB |
ok, no valid answer |
91 |
Correct |
9 ms |
14668 KB |
ok, no valid answer |
92 |
Correct |
11 ms |
14668 KB |
ok, no valid answer |
93 |
Correct |
9 ms |
14668 KB |
ok, no valid answer |
94 |
Correct |
88 ms |
27164 KB |
ok, correct split |
95 |
Correct |
127 ms |
32240 KB |
ok, correct split |
96 |
Correct |
110 ms |
30560 KB |
ok, correct split |
97 |
Correct |
32 ms |
18372 KB |
ok, correct split |
98 |
Correct |
32 ms |
18500 KB |
ok, correct split |
99 |
Correct |
45 ms |
20788 KB |
ok, correct split |
100 |
Correct |
129 ms |
27976 KB |
ok, correct split |
101 |
Correct |
131 ms |
26844 KB |
ok, correct split |
102 |
Correct |
94 ms |
26580 KB |
ok, correct split |
103 |
Correct |
89 ms |
26428 KB |
ok, correct split |
104 |
Correct |
86 ms |
28156 KB |
ok, correct split |
105 |
Correct |
50 ms |
21348 KB |
ok, correct split |
106 |
Correct |
99 ms |
32708 KB |
ok, correct split |
107 |
Correct |
80 ms |
25276 KB |
ok, correct split |
108 |
Correct |
115 ms |
24996 KB |
ok, correct split |
109 |
Correct |
118 ms |
28032 KB |
ok, correct split |
110 |
Correct |
116 ms |
29236 KB |
ok, correct split |
111 |
Correct |
117 ms |
29116 KB |
ok, correct split |
112 |
Correct |
114 ms |
29512 KB |
ok, correct split |
113 |
Correct |
117 ms |
29308 KB |
ok, correct split |
114 |
Correct |
17 ms |
16052 KB |
ok, correct split |
115 |
Correct |
16 ms |
15824 KB |
ok, correct split |
116 |
Correct |
105 ms |
28864 KB |
ok, correct split |
117 |
Correct |
109 ms |
28732 KB |
ok, correct split |
118 |
Correct |
80 ms |
24372 KB |
ok, correct split |
119 |
Correct |
77 ms |
24260 KB |
ok, correct split |
120 |
Correct |
90 ms |
28340 KB |
ok, correct split |
121 |
Correct |
79 ms |
25332 KB |
ok, no valid answer |
122 |
Correct |
84 ms |
25356 KB |
ok, no valid answer |
123 |
Correct |
117 ms |
28740 KB |
ok, no valid answer |
124 |
Correct |
127 ms |
28880 KB |
ok, no valid answer |
125 |
Correct |
77 ms |
26632 KB |
ok, no valid answer |
126 |
Correct |
56 ms |
24668 KB |
ok, no valid answer |
127 |
Correct |
97 ms |
26948 KB |
ok, no valid answer |