#include<bits/stdc++.h>
#include "split.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 1e5 ;
bool us[N + 1] ;
int vert, sz[N + 1], ind[N + 1] ;
vector<int> ts, res, v[N + 1], other[N + 1], tree[N + 1] ;
void ultra_clear()
{
for(int i = 0 ; i < N ; i++)
us[i] = 0 ;
}
void build_tree(int city)
{
us[city] = 1 ;
for(int i : v[city])
{
if(us[i])
continue ;
tree[city].push_back(i) ;
build_tree(i) ;
}
}
void dfs_for_tree(int city, int a1)
{
ind[city] = ts.size() ;
ts.push_back(city) ;
sz[city]++ ;
int mx = 0 ;
for(int i : tree[city])
{
dfs_for_tree(i, a1) ;
mx = max(mx, sz[i]) ;
sz[city] += sz[i] ;
}
if(mx < a1 && sz[city] >= a1)
vert = city ;
}
void dfs_color(int city, int &cnt, int color)
{
us[city] = 1 ;
if(cnt)
{
cnt-- ;
res[city] = color ;
}
for(int i : tree[city])
{
if(us[i])
continue ;
dfs_color(i, cnt, color) ;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> fr, vector<int> to)
{
vector<pair<int, int>> all = {{a, 1}, {b, 2}, {c, 3}} ;
sort(all.begin(), all.end()) ;
int m = fr.size() ;
for(int i = 0 ; i < n ; i++)
res.push_back(0) ;
for(int i = 0 ; i < m ; i++)
{
v[fr[i]].push_back(to[i]) ;
v[to[i]].push_back(fr[i]) ;
}
build_tree(0) ;
dfs_for_tree(0, all[0].fi) ;
for(int i = 0 ; i < m ; i++)
{
int f = fr[i], t = to[i] ;
if(ind[vert] <= ind[f] && ind[f] < ind[vert] + sz[vert] && ind[t] < ind[vert])
other[f].push_back(t) ;
if(ind[vert] <= ind[t] && ind[t] < ind[vert] + sz[vert] && ind[f] < ind[vert])
other[t].push_back(f) ;
}
vector<int> del ;
for(int i = ind[vert] + 1 ; i < ind[vert] + sz[vert] ; i++)
{
int now = ts[i] ;
if(sz[vert] - sz[now] >= all[0].fi && other[now].size())
{
del.push_back(now) ;
tree[other[now][0]].push_back(now) ;
us[now] = 1 ;
sz[vert] -= sz[now] ;
i = ind[now] + sz[now] - 1 ;
}
}
if(sz[vert] >= all[0].fi && n - sz[vert] >= all[1].fi)
{
ultra_clear() ;
for(int i : del)
us[i] = 1 ;
dfs_color(vert, all[0].fi, all[0].se) ;
for(int i : del)
us[i] = 0 ;
dfs_color(0, all[1].fi, all[1].se) ;
for(int i = 0 ; i < n ; i++)
if(!res[i])
res[i] = all[2].se ;
}
else
{
if(sz[vert] >= all[1].fi && n - sz[vert] >= all[0].fi)
{
ultra_clear() ;
for(int i : del)
us[i] = 1 ;
dfs_color(vert, all[1].fi, all[1].se) ;
for(int i : del)
us[i] = 0 ;
dfs_color(0, all[0].fi, all[0].se) ;
for(int i = 0 ; i < n ; i++)
if(!res[i])
res[i] = all[2].se ;
}
}
return res ;
}
//signed main()
//{
// ios_base::sync_with_stdio( 0 ) ;
// cin.tie( 0 ) ;
// cout.tie( 0 ) ;
// int n, m, a, b, c ;
// cin >> n >> a >> b >> c >> m ;
// vector<int> fr(m), to(m) ;
// for(int i = 0 ; i < m ; i++)
// cin >> fr[i] >> to[i] ;
// vector<int> ans = find_split(n, a, b, c, fr, to) ;
// for(int i : ans)
// cout << i << ' ' ;
// return 0 ;
//}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7380 KB |
ok, correct split |
2 |
Correct |
3 ms |
7352 KB |
ok, correct split |
3 |
Correct |
3 ms |
7380 KB |
ok, correct split |
4 |
Correct |
4 ms |
7352 KB |
ok, correct split |
5 |
Correct |
3 ms |
7380 KB |
ok, correct split |
6 |
Correct |
3 ms |
7352 KB |
ok, correct split |
7 |
Correct |
65 ms |
24948 KB |
ok, correct split |
8 |
Correct |
70 ms |
22700 KB |
ok, correct split |
9 |
Correct |
75 ms |
22084 KB |
ok, correct split |
10 |
Correct |
97 ms |
25320 KB |
ok, correct split |
11 |
Correct |
65 ms |
25336 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7356 KB |
ok, correct split |
2 |
Correct |
3 ms |
7380 KB |
ok, correct split |
3 |
Correct |
3 ms |
7380 KB |
ok, correct split |
4 |
Correct |
72 ms |
21184 KB |
ok, correct split |
5 |
Correct |
53 ms |
16092 KB |
ok, correct split |
6 |
Correct |
62 ms |
25320 KB |
ok, correct split |
7 |
Correct |
77 ms |
22512 KB |
ok, correct split |
8 |
Correct |
81 ms |
18948 KB |
ok, correct split |
9 |
Correct |
59 ms |
17592 KB |
ok, correct split |
10 |
Correct |
42 ms |
15204 KB |
ok, correct split |
11 |
Correct |
41 ms |
15244 KB |
ok, correct split |
12 |
Correct |
46 ms |
15368 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7352 KB |
ok, correct split |
2 |
Correct |
63 ms |
16096 KB |
ok, correct split |
3 |
Correct |
23 ms |
11416 KB |
ok, correct split |
4 |
Correct |
5 ms |
7352 KB |
ok, correct split |
5 |
Correct |
62 ms |
21044 KB |
ok, correct split |
6 |
Correct |
57 ms |
20804 KB |
ok, correct split |
7 |
Correct |
57 ms |
20676 KB |
ok, correct split |
8 |
Correct |
60 ms |
21972 KB |
ok, correct split |
9 |
Correct |
64 ms |
20444 KB |
ok, correct split |
10 |
Correct |
18 ms |
10680 KB |
ok, no valid answer |
11 |
Correct |
26 ms |
12152 KB |
ok, no valid answer |
12 |
Correct |
44 ms |
16460 KB |
ok, no valid answer |
13 |
Correct |
52 ms |
16968 KB |
ok, no valid answer |
14 |
Correct |
42 ms |
16060 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7380 KB |
ok, correct split |
2 |
Correct |
3 ms |
7352 KB |
ok, no valid answer |
3 |
Correct |
3 ms |
7372 KB |
ok, correct split |
4 |
Correct |
3 ms |
7380 KB |
ok, correct split |
5 |
Correct |
3 ms |
7360 KB |
ok, correct split |
6 |
Correct |
3 ms |
7432 KB |
ok, correct split |
7 |
Correct |
3 ms |
7380 KB |
ok, correct split |
8 |
Correct |
3 ms |
7356 KB |
ok, correct split |
9 |
Correct |
5 ms |
7752 KB |
ok, correct split |
10 |
Correct |
5 ms |
7752 KB |
ok, correct split |
11 |
Correct |
5 ms |
7508 KB |
ok, correct split |
12 |
Correct |
7 ms |
7764 KB |
ok, correct split |
13 |
Correct |
3 ms |
7380 KB |
ok, correct split |
14 |
Correct |
3 ms |
7380 KB |
ok, correct split |
15 |
Correct |
3 ms |
7352 KB |
ok, correct split |
16 |
Correct |
3 ms |
7360 KB |
ok, correct split |
17 |
Correct |
3 ms |
7380 KB |
ok, correct split |
18 |
Correct |
3 ms |
7352 KB |
ok, correct split |
19 |
Correct |
4 ms |
7508 KB |
ok, correct split |
20 |
Correct |
4 ms |
7492 KB |
ok, correct split |
21 |
Correct |
4 ms |
7764 KB |
ok, correct split |
22 |
Correct |
4 ms |
7764 KB |
ok, correct split |
23 |
Correct |
4 ms |
7756 KB |
ok, correct split |
24 |
Correct |
5 ms |
7752 KB |
ok, correct split |
25 |
Correct |
4 ms |
7764 KB |
ok, correct split |
26 |
Correct |
5 ms |
7772 KB |
ok, correct split |
27 |
Correct |
5 ms |
7804 KB |
ok, correct split |
28 |
Correct |
5 ms |
7692 KB |
ok, correct split |
29 |
Correct |
4 ms |
7380 KB |
ok, correct split |
30 |
Correct |
7 ms |
7764 KB |
ok, correct split |
31 |
Correct |
4 ms |
7508 KB |
ok, correct split |
32 |
Correct |
4 ms |
7484 KB |
ok, correct split |
33 |
Correct |
4 ms |
7408 KB |
ok, correct split |
34 |
Correct |
5 ms |
7624 KB |
ok, correct split |
35 |
Correct |
4 ms |
7616 KB |
ok, correct split |
36 |
Correct |
5 ms |
7636 KB |
ok, correct split |
37 |
Correct |
5 ms |
7764 KB |
ok, correct split |
38 |
Correct |
5 ms |
7892 KB |
ok, correct split |
39 |
Correct |
5 ms |
7816 KB |
ok, correct split |
40 |
Correct |
6 ms |
7756 KB |
ok, correct split |
41 |
Correct |
5 ms |
7508 KB |
ok, correct split |
42 |
Correct |
4 ms |
7508 KB |
ok, correct split |
43 |
Correct |
5 ms |
7764 KB |
ok, correct split |
44 |
Correct |
6 ms |
7712 KB |
ok, correct split |
45 |
Correct |
5 ms |
7860 KB |
ok, correct split |
46 |
Correct |
4 ms |
7752 KB |
ok, correct split |
47 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
48 |
Correct |
6 ms |
7648 KB |
ok, correct split |
49 |
Correct |
4 ms |
7764 KB |
ok, correct split |
50 |
Correct |
3 ms |
7252 KB |
ok, no valid answer |
51 |
Correct |
3 ms |
7252 KB |
ok, no valid answer |
52 |
Correct |
4 ms |
7508 KB |
ok, no valid answer |
53 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
54 |
Correct |
4 ms |
7500 KB |
ok, no valid answer |
55 |
Correct |
4 ms |
7592 KB |
ok, no valid answer |
56 |
Correct |
4 ms |
7620 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7380 KB |
ok, correct split |
2 |
Correct |
3 ms |
7352 KB |
ok, correct split |
3 |
Correct |
3 ms |
7380 KB |
ok, correct split |
4 |
Correct |
4 ms |
7352 KB |
ok, correct split |
5 |
Correct |
3 ms |
7380 KB |
ok, correct split |
6 |
Correct |
3 ms |
7352 KB |
ok, correct split |
7 |
Correct |
65 ms |
24948 KB |
ok, correct split |
8 |
Correct |
70 ms |
22700 KB |
ok, correct split |
9 |
Correct |
75 ms |
22084 KB |
ok, correct split |
10 |
Correct |
97 ms |
25320 KB |
ok, correct split |
11 |
Correct |
65 ms |
25336 KB |
ok, correct split |
12 |
Correct |
3 ms |
7356 KB |
ok, correct split |
13 |
Correct |
3 ms |
7380 KB |
ok, correct split |
14 |
Correct |
3 ms |
7380 KB |
ok, correct split |
15 |
Correct |
72 ms |
21184 KB |
ok, correct split |
16 |
Correct |
53 ms |
16092 KB |
ok, correct split |
17 |
Correct |
62 ms |
25320 KB |
ok, correct split |
18 |
Correct |
77 ms |
22512 KB |
ok, correct split |
19 |
Correct |
81 ms |
18948 KB |
ok, correct split |
20 |
Correct |
59 ms |
17592 KB |
ok, correct split |
21 |
Correct |
42 ms |
15204 KB |
ok, correct split |
22 |
Correct |
41 ms |
15244 KB |
ok, correct split |
23 |
Correct |
46 ms |
15368 KB |
ok, correct split |
24 |
Correct |
3 ms |
7352 KB |
ok, correct split |
25 |
Correct |
63 ms |
16096 KB |
ok, correct split |
26 |
Correct |
23 ms |
11416 KB |
ok, correct split |
27 |
Correct |
5 ms |
7352 KB |
ok, correct split |
28 |
Correct |
62 ms |
21044 KB |
ok, correct split |
29 |
Correct |
57 ms |
20804 KB |
ok, correct split |
30 |
Correct |
57 ms |
20676 KB |
ok, correct split |
31 |
Correct |
60 ms |
21972 KB |
ok, correct split |
32 |
Correct |
64 ms |
20444 KB |
ok, correct split |
33 |
Correct |
18 ms |
10680 KB |
ok, no valid answer |
34 |
Correct |
26 ms |
12152 KB |
ok, no valid answer |
35 |
Correct |
44 ms |
16460 KB |
ok, no valid answer |
36 |
Correct |
52 ms |
16968 KB |
ok, no valid answer |
37 |
Correct |
42 ms |
16060 KB |
ok, no valid answer |
38 |
Correct |
3 ms |
7380 KB |
ok, correct split |
39 |
Correct |
3 ms |
7352 KB |
ok, no valid answer |
40 |
Correct |
3 ms |
7372 KB |
ok, correct split |
41 |
Correct |
3 ms |
7380 KB |
ok, correct split |
42 |
Correct |
3 ms |
7360 KB |
ok, correct split |
43 |
Correct |
3 ms |
7432 KB |
ok, correct split |
44 |
Correct |
3 ms |
7380 KB |
ok, correct split |
45 |
Correct |
3 ms |
7356 KB |
ok, correct split |
46 |
Correct |
5 ms |
7752 KB |
ok, correct split |
47 |
Correct |
5 ms |
7752 KB |
ok, correct split |
48 |
Correct |
5 ms |
7508 KB |
ok, correct split |
49 |
Correct |
7 ms |
7764 KB |
ok, correct split |
50 |
Correct |
3 ms |
7380 KB |
ok, correct split |
51 |
Correct |
3 ms |
7380 KB |
ok, correct split |
52 |
Correct |
3 ms |
7352 KB |
ok, correct split |
53 |
Correct |
3 ms |
7360 KB |
ok, correct split |
54 |
Correct |
3 ms |
7380 KB |
ok, correct split |
55 |
Correct |
3 ms |
7352 KB |
ok, correct split |
56 |
Correct |
4 ms |
7508 KB |
ok, correct split |
57 |
Correct |
4 ms |
7492 KB |
ok, correct split |
58 |
Correct |
4 ms |
7764 KB |
ok, correct split |
59 |
Correct |
4 ms |
7764 KB |
ok, correct split |
60 |
Correct |
4 ms |
7756 KB |
ok, correct split |
61 |
Correct |
5 ms |
7752 KB |
ok, correct split |
62 |
Correct |
4 ms |
7764 KB |
ok, correct split |
63 |
Correct |
5 ms |
7772 KB |
ok, correct split |
64 |
Correct |
5 ms |
7804 KB |
ok, correct split |
65 |
Correct |
5 ms |
7692 KB |
ok, correct split |
66 |
Correct |
4 ms |
7380 KB |
ok, correct split |
67 |
Correct |
7 ms |
7764 KB |
ok, correct split |
68 |
Correct |
4 ms |
7508 KB |
ok, correct split |
69 |
Correct |
4 ms |
7484 KB |
ok, correct split |
70 |
Correct |
4 ms |
7408 KB |
ok, correct split |
71 |
Correct |
5 ms |
7624 KB |
ok, correct split |
72 |
Correct |
4 ms |
7616 KB |
ok, correct split |
73 |
Correct |
5 ms |
7636 KB |
ok, correct split |
74 |
Correct |
5 ms |
7764 KB |
ok, correct split |
75 |
Correct |
5 ms |
7892 KB |
ok, correct split |
76 |
Correct |
5 ms |
7816 KB |
ok, correct split |
77 |
Correct |
6 ms |
7756 KB |
ok, correct split |
78 |
Correct |
5 ms |
7508 KB |
ok, correct split |
79 |
Correct |
4 ms |
7508 KB |
ok, correct split |
80 |
Correct |
5 ms |
7764 KB |
ok, correct split |
81 |
Correct |
6 ms |
7712 KB |
ok, correct split |
82 |
Correct |
5 ms |
7860 KB |
ok, correct split |
83 |
Correct |
4 ms |
7752 KB |
ok, correct split |
84 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
85 |
Correct |
6 ms |
7648 KB |
ok, correct split |
86 |
Correct |
4 ms |
7764 KB |
ok, correct split |
87 |
Correct |
3 ms |
7252 KB |
ok, no valid answer |
88 |
Correct |
3 ms |
7252 KB |
ok, no valid answer |
89 |
Correct |
4 ms |
7508 KB |
ok, no valid answer |
90 |
Correct |
5 ms |
7636 KB |
ok, no valid answer |
91 |
Correct |
4 ms |
7500 KB |
ok, no valid answer |
92 |
Correct |
4 ms |
7592 KB |
ok, no valid answer |
93 |
Correct |
4 ms |
7620 KB |
ok, no valid answer |
94 |
Correct |
64 ms |
20168 KB |
ok, correct split |
95 |
Correct |
92 ms |
26440 KB |
ok, correct split |
96 |
Correct |
112 ms |
24476 KB |
ok, correct split |
97 |
Correct |
22 ms |
11332 KB |
ok, correct split |
98 |
Correct |
24 ms |
11516 KB |
ok, correct split |
99 |
Correct |
35 ms |
13924 KB |
ok, correct split |
100 |
Correct |
93 ms |
21336 KB |
ok, correct split |
101 |
Correct |
70 ms |
20196 KB |
ok, correct split |
102 |
Correct |
68 ms |
19512 KB |
ok, correct split |
103 |
Correct |
72 ms |
19280 KB |
ok, correct split |
104 |
Correct |
68 ms |
20408 KB |
ok, correct split |
105 |
Correct |
34 ms |
13636 KB |
ok, correct split |
106 |
Correct |
76 ms |
22828 KB |
ok, correct split |
107 |
Correct |
54 ms |
17096 KB |
ok, correct split |
108 |
Correct |
68 ms |
17060 KB |
ok, correct split |
109 |
Correct |
78 ms |
20664 KB |
ok, correct split |
110 |
Correct |
86 ms |
24504 KB |
ok, correct split |
111 |
Correct |
84 ms |
24636 KB |
ok, correct split |
112 |
Correct |
83 ms |
23292 KB |
ok, correct split |
113 |
Correct |
91 ms |
23364 KB |
ok, correct split |
114 |
Correct |
11 ms |
9164 KB |
ok, correct split |
115 |
Correct |
12 ms |
8984 KB |
ok, correct split |
116 |
Correct |
81 ms |
24500 KB |
ok, correct split |
117 |
Correct |
86 ms |
24208 KB |
ok, correct split |
118 |
Correct |
82 ms |
18728 KB |
ok, correct split |
119 |
Correct |
54 ms |
18568 KB |
ok, correct split |
120 |
Correct |
64 ms |
22636 KB |
ok, correct split |
121 |
Correct |
52 ms |
17096 KB |
ok, no valid answer |
122 |
Correct |
50 ms |
17012 KB |
ok, no valid answer |
123 |
Correct |
103 ms |
21720 KB |
ok, no valid answer |
124 |
Correct |
86 ms |
21360 KB |
ok, no valid answer |
125 |
Correct |
51 ms |
17916 KB |
ok, no valid answer |
126 |
Correct |
35 ms |
15256 KB |
ok, no valid answer |
127 |
Correct |
66 ms |
18804 KB |
ok, no valid answer |