#include <bits/stdc++.h>
using namespace std;
const int n_max = 2e5+1e3;
int visit[n_max];
int low[n_max];
int subtree[n_max];
vector<int> adj[n_max];
vector<int> child[n_max];
int parent[n_max];
int time_global = 0;
void dfs(int x) {
subtree[x] = 1;
visit[x] = time_global;
time_global++;
low[x] = visit[x];
for(int i: adj[x]) {
if(visit[i]==-1) {
parent[i] = x;
child[x].push_back(i);
dfs(i);
subtree[x] += subtree[i];
low[x] = min(low[x], low[i]);
} else if (i != parent[x]) {
low[x] = min(low[x], visit[i]);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
// assume a<=b<=c
vector<pair<int,int>> vp = {make_pair(a,1),make_pair(b,2),make_pair(c,3)};
sort(vp.begin(), vp.end());
int small = vp[0].second;
int mid = vp[1].second;
int big = vp[2].second;
a = vp[0].first;
b = vp[1].first;
c = vp[2].first;
memset(visit, -1, sizeof(visit));
for(int i=0; i<(int) p.size(); i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs(0);
vector<int> ans(n,0);
for(int i=0; i<n; i++) {
// assume c>=a
// check: a+c or b+c?
if(subtree[i]>=a && subtree[i]<=b+c) {
if(subtree[i]>a+c) {
swap(a,b);
swap(small,mid);
}
queue<int> bfs;
bfs.push(i);
int ctr = 0;
while(!bfs.empty()) {
int next = bfs.front();
ans[next] = (ctr<a ? small : big);
ctr++;
bfs.pop();
for(int k: child[next]) {
bfs.push(k);
}
}
bfs.push(0);
ctr = 0;
while(!bfs.empty()) {
int next = bfs.front();
ans[next] = (ctr<b ? mid : big);
ctr++;
bfs.pop();
for(int k: child[next]) {
if(ans[k]==0) {
bfs.push(k);
}
}
}
for(int k=0; k<n; k++) {
assert(ans[k]!=0);
}
return ans;
} else if(subtree[i]>b+c) {
// if have heavy node with all light children
bool all_light = true;
for(int j: child[i]) {
if(subtree[j]>=a) {
all_light = false;
// break;
}
}
if(all_light) {
if(i==0) {
assert(child[i].size()>=3);
return ans;
}
int minsize = 1;
vector<int> tmp; // consists of all the children to be taken
for(int j: child[i]) {
// add all those with bad lowtime
if(low[j]>= visit[i]) {
minsize += subtree[j];
tmp.push_back(j);
}
}
if(minsize > b+c) {
return ans;
}
for(int j: child[i]) {
// add the relevant subtrees
if(low[j]<visit[i] && minsize < b) {
minsize += subtree[j];
tmp.push_back(j);
}
}
assert(minsize >= b);
assert(minsize <= b+c);
// now for each subtree, color its children completely except that some are colored with 3
int ctr = 1;
ans[i] = mid;
queue<int> bfs;
for(int j: tmp) {
bfs.push(j);
while(!bfs.empty()) {
int next = bfs.front();
assert(ans[next]==0);
ans[next] = (ctr<b ? mid : big);
ctr++;
bfs.pop();
for(int k: child[next]) {
bfs.push(k);
}
}
}
//assert(ctr==b);
ctr = 1;
bfs.push(0); // we know that 0 is not the root
ans[0] = small;
while(!bfs.empty()) {
int next = bfs.front();
bfs.pop();
for(int k: adj[next]) {
if(ans[k]==0) {
bfs.push(k);
ans[k] = (ctr<a ? small : big);
ctr++;
}
}
}
//assert(ctr==a);
for(int k=0; k<n; k++) {
//assert(ans[k]!=0);
}
return ans;
}
}
}
assert(false);
return p;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10488 KB |
ok, correct split |
2 |
Correct |
10 ms |
10488 KB |
ok, correct split |
3 |
Correct |
11 ms |
10616 KB |
ok, correct split |
4 |
Correct |
10 ms |
10488 KB |
ok, correct split |
5 |
Correct |
11 ms |
10488 KB |
ok, correct split |
6 |
Correct |
11 ms |
10488 KB |
ok, correct split |
7 |
Correct |
136 ms |
27384 KB |
ok, correct split |
8 |
Correct |
133 ms |
25080 KB |
ok, correct split |
9 |
Correct |
131 ms |
24440 KB |
ok, correct split |
10 |
Correct |
131 ms |
27768 KB |
ok, correct split |
11 |
Correct |
139 ms |
27768 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10488 KB |
ok, correct split |
2 |
Correct |
11 ms |
10552 KB |
ok, correct split |
3 |
Correct |
10 ms |
10588 KB |
ok, correct split |
4 |
Correct |
154 ms |
23584 KB |
ok, correct split |
5 |
Correct |
110 ms |
18680 KB |
ok, correct split |
6 |
Correct |
141 ms |
27768 KB |
ok, correct split |
7 |
Correct |
134 ms |
24952 KB |
ok, correct split |
8 |
Correct |
167 ms |
21240 KB |
ok, correct split |
9 |
Correct |
126 ms |
20088 KB |
ok, correct split |
10 |
Correct |
73 ms |
18032 KB |
ok, correct split |
11 |
Correct |
73 ms |
18028 KB |
ok, correct split |
12 |
Correct |
81 ms |
18032 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10484 KB |
ok, correct split |
2 |
Correct |
117 ms |
18680 KB |
ok, correct split |
3 |
Correct |
45 ms |
13820 KB |
ok, correct split |
4 |
Correct |
11 ms |
10616 KB |
ok, correct split |
5 |
Correct |
130 ms |
22520 KB |
ok, correct split |
6 |
Correct |
133 ms |
22364 KB |
ok, correct split |
7 |
Correct |
137 ms |
22008 KB |
ok, correct split |
8 |
Correct |
128 ms |
23516 KB |
ok, correct split |
9 |
Correct |
135 ms |
21984 KB |
ok, correct split |
10 |
Correct |
38 ms |
13224 KB |
ok, no valid answer |
11 |
Correct |
52 ms |
14584 KB |
ok, no valid answer |
12 |
Correct |
111 ms |
18420 KB |
ok, no valid answer |
13 |
Correct |
132 ms |
18628 KB |
ok, no valid answer |
14 |
Correct |
76 ms |
18404 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10488 KB |
ok, correct split |
2 |
Correct |
12 ms |
10616 KB |
ok, no valid answer |
3 |
Correct |
12 ms |
10616 KB |
ok, correct split |
4 |
Correct |
11 ms |
10616 KB |
ok, correct split |
5 |
Correct |
11 ms |
10616 KB |
ok, correct split |
6 |
Correct |
11 ms |
10616 KB |
ok, correct split |
7 |
Correct |
11 ms |
10556 KB |
ok, correct split |
8 |
Correct |
11 ms |
10616 KB |
ok, correct split |
9 |
Correct |
13 ms |
10872 KB |
ok, correct split |
10 |
Correct |
14 ms |
10872 KB |
ok, correct split |
11 |
Correct |
11 ms |
10620 KB |
ok, correct split |
12 |
Correct |
13 ms |
10872 KB |
ok, correct split |
13 |
Correct |
11 ms |
10616 KB |
ok, correct split |
14 |
Correct |
11 ms |
10488 KB |
ok, correct split |
15 |
Correct |
11 ms |
10620 KB |
ok, correct split |
16 |
Correct |
11 ms |
10488 KB |
ok, correct split |
17 |
Correct |
11 ms |
10616 KB |
ok, correct split |
18 |
Correct |
11 ms |
10616 KB |
ok, correct split |
19 |
Correct |
11 ms |
10616 KB |
ok, correct split |
20 |
Correct |
12 ms |
10616 KB |
ok, correct split |
21 |
Correct |
15 ms |
10872 KB |
ok, correct split |
22 |
Correct |
13 ms |
10872 KB |
ok, correct split |
23 |
Correct |
13 ms |
10872 KB |
ok, correct split |
24 |
Correct |
13 ms |
10872 KB |
ok, correct split |
25 |
Correct |
12 ms |
10876 KB |
ok, correct split |
26 |
Correct |
13 ms |
10872 KB |
ok, correct split |
27 |
Correct |
15 ms |
10748 KB |
ok, correct split |
28 |
Correct |
14 ms |
10744 KB |
ok, correct split |
29 |
Correct |
11 ms |
10616 KB |
ok, correct split |
30 |
Correct |
13 ms |
10744 KB |
ok, correct split |
31 |
Correct |
12 ms |
10616 KB |
ok, correct split |
32 |
Correct |
11 ms |
10616 KB |
ok, correct split |
33 |
Correct |
11 ms |
10616 KB |
ok, correct split |
34 |
Correct |
13 ms |
10744 KB |
ok, correct split |
35 |
Correct |
13 ms |
10744 KB |
ok, correct split |
36 |
Correct |
13 ms |
10744 KB |
ok, correct split |
37 |
Correct |
14 ms |
10876 KB |
ok, correct split |
38 |
Correct |
14 ms |
11000 KB |
ok, correct split |
39 |
Correct |
13 ms |
10872 KB |
ok, correct split |
40 |
Correct |
14 ms |
10872 KB |
ok, correct split |
41 |
Correct |
12 ms |
10744 KB |
ok, correct split |
42 |
Correct |
12 ms |
10616 KB |
ok, correct split |
43 |
Correct |
14 ms |
10780 KB |
ok, correct split |
44 |
Correct |
14 ms |
10872 KB |
ok, correct split |
45 |
Correct |
13 ms |
10872 KB |
ok, correct split |
46 |
Correct |
13 ms |
10872 KB |
ok, correct split |
47 |
Correct |
13 ms |
10872 KB |
ok, no valid answer |
48 |
Correct |
13 ms |
10872 KB |
ok, correct split |
49 |
Correct |
13 ms |
10872 KB |
ok, correct split |
50 |
Correct |
11 ms |
10488 KB |
ok, no valid answer |
51 |
Correct |
11 ms |
10616 KB |
ok, no valid answer |
52 |
Correct |
13 ms |
10744 KB |
ok, no valid answer |
53 |
Correct |
16 ms |
10872 KB |
ok, no valid answer |
54 |
Correct |
13 ms |
10744 KB |
ok, no valid answer |
55 |
Correct |
13 ms |
10872 KB |
ok, no valid answer |
56 |
Correct |
13 ms |
10744 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10488 KB |
ok, correct split |
2 |
Correct |
10 ms |
10488 KB |
ok, correct split |
3 |
Correct |
11 ms |
10616 KB |
ok, correct split |
4 |
Correct |
10 ms |
10488 KB |
ok, correct split |
5 |
Correct |
11 ms |
10488 KB |
ok, correct split |
6 |
Correct |
11 ms |
10488 KB |
ok, correct split |
7 |
Correct |
136 ms |
27384 KB |
ok, correct split |
8 |
Correct |
133 ms |
25080 KB |
ok, correct split |
9 |
Correct |
131 ms |
24440 KB |
ok, correct split |
10 |
Correct |
131 ms |
27768 KB |
ok, correct split |
11 |
Correct |
139 ms |
27768 KB |
ok, correct split |
12 |
Correct |
10 ms |
10488 KB |
ok, correct split |
13 |
Correct |
11 ms |
10552 KB |
ok, correct split |
14 |
Correct |
10 ms |
10588 KB |
ok, correct split |
15 |
Correct |
154 ms |
23584 KB |
ok, correct split |
16 |
Correct |
110 ms |
18680 KB |
ok, correct split |
17 |
Correct |
141 ms |
27768 KB |
ok, correct split |
18 |
Correct |
134 ms |
24952 KB |
ok, correct split |
19 |
Correct |
167 ms |
21240 KB |
ok, correct split |
20 |
Correct |
126 ms |
20088 KB |
ok, correct split |
21 |
Correct |
73 ms |
18032 KB |
ok, correct split |
22 |
Correct |
73 ms |
18028 KB |
ok, correct split |
23 |
Correct |
81 ms |
18032 KB |
ok, correct split |
24 |
Correct |
11 ms |
10484 KB |
ok, correct split |
25 |
Correct |
117 ms |
18680 KB |
ok, correct split |
26 |
Correct |
45 ms |
13820 KB |
ok, correct split |
27 |
Correct |
11 ms |
10616 KB |
ok, correct split |
28 |
Correct |
130 ms |
22520 KB |
ok, correct split |
29 |
Correct |
133 ms |
22364 KB |
ok, correct split |
30 |
Correct |
137 ms |
22008 KB |
ok, correct split |
31 |
Correct |
128 ms |
23516 KB |
ok, correct split |
32 |
Correct |
135 ms |
21984 KB |
ok, correct split |
33 |
Correct |
38 ms |
13224 KB |
ok, no valid answer |
34 |
Correct |
52 ms |
14584 KB |
ok, no valid answer |
35 |
Correct |
111 ms |
18420 KB |
ok, no valid answer |
36 |
Correct |
132 ms |
18628 KB |
ok, no valid answer |
37 |
Correct |
76 ms |
18404 KB |
ok, no valid answer |
38 |
Correct |
11 ms |
10488 KB |
ok, correct split |
39 |
Correct |
12 ms |
10616 KB |
ok, no valid answer |
40 |
Correct |
12 ms |
10616 KB |
ok, correct split |
41 |
Correct |
11 ms |
10616 KB |
ok, correct split |
42 |
Correct |
11 ms |
10616 KB |
ok, correct split |
43 |
Correct |
11 ms |
10616 KB |
ok, correct split |
44 |
Correct |
11 ms |
10556 KB |
ok, correct split |
45 |
Correct |
11 ms |
10616 KB |
ok, correct split |
46 |
Correct |
13 ms |
10872 KB |
ok, correct split |
47 |
Correct |
14 ms |
10872 KB |
ok, correct split |
48 |
Correct |
11 ms |
10620 KB |
ok, correct split |
49 |
Correct |
13 ms |
10872 KB |
ok, correct split |
50 |
Correct |
11 ms |
10616 KB |
ok, correct split |
51 |
Correct |
11 ms |
10488 KB |
ok, correct split |
52 |
Correct |
11 ms |
10620 KB |
ok, correct split |
53 |
Correct |
11 ms |
10488 KB |
ok, correct split |
54 |
Correct |
11 ms |
10616 KB |
ok, correct split |
55 |
Correct |
11 ms |
10616 KB |
ok, correct split |
56 |
Correct |
11 ms |
10616 KB |
ok, correct split |
57 |
Correct |
12 ms |
10616 KB |
ok, correct split |
58 |
Correct |
15 ms |
10872 KB |
ok, correct split |
59 |
Correct |
13 ms |
10872 KB |
ok, correct split |
60 |
Correct |
13 ms |
10872 KB |
ok, correct split |
61 |
Correct |
13 ms |
10872 KB |
ok, correct split |
62 |
Correct |
12 ms |
10876 KB |
ok, correct split |
63 |
Correct |
13 ms |
10872 KB |
ok, correct split |
64 |
Correct |
15 ms |
10748 KB |
ok, correct split |
65 |
Correct |
14 ms |
10744 KB |
ok, correct split |
66 |
Correct |
11 ms |
10616 KB |
ok, correct split |
67 |
Correct |
13 ms |
10744 KB |
ok, correct split |
68 |
Correct |
12 ms |
10616 KB |
ok, correct split |
69 |
Correct |
11 ms |
10616 KB |
ok, correct split |
70 |
Correct |
11 ms |
10616 KB |
ok, correct split |
71 |
Correct |
13 ms |
10744 KB |
ok, correct split |
72 |
Correct |
13 ms |
10744 KB |
ok, correct split |
73 |
Correct |
13 ms |
10744 KB |
ok, correct split |
74 |
Correct |
14 ms |
10876 KB |
ok, correct split |
75 |
Correct |
14 ms |
11000 KB |
ok, correct split |
76 |
Correct |
13 ms |
10872 KB |
ok, correct split |
77 |
Correct |
14 ms |
10872 KB |
ok, correct split |
78 |
Correct |
12 ms |
10744 KB |
ok, correct split |
79 |
Correct |
12 ms |
10616 KB |
ok, correct split |
80 |
Correct |
14 ms |
10780 KB |
ok, correct split |
81 |
Correct |
14 ms |
10872 KB |
ok, correct split |
82 |
Correct |
13 ms |
10872 KB |
ok, correct split |
83 |
Correct |
13 ms |
10872 KB |
ok, correct split |
84 |
Correct |
13 ms |
10872 KB |
ok, no valid answer |
85 |
Correct |
13 ms |
10872 KB |
ok, correct split |
86 |
Correct |
13 ms |
10872 KB |
ok, correct split |
87 |
Correct |
11 ms |
10488 KB |
ok, no valid answer |
88 |
Correct |
11 ms |
10616 KB |
ok, no valid answer |
89 |
Correct |
13 ms |
10744 KB |
ok, no valid answer |
90 |
Correct |
16 ms |
10872 KB |
ok, no valid answer |
91 |
Correct |
13 ms |
10744 KB |
ok, no valid answer |
92 |
Correct |
13 ms |
10872 KB |
ok, no valid answer |
93 |
Correct |
13 ms |
10744 KB |
ok, no valid answer |
94 |
Correct |
131 ms |
21496 KB |
ok, correct split |
95 |
Correct |
177 ms |
26232 KB |
ok, correct split |
96 |
Correct |
163 ms |
24824 KB |
ok, correct split |
97 |
Correct |
45 ms |
13816 KB |
ok, correct split |
98 |
Correct |
49 ms |
13944 KB |
ok, correct split |
99 |
Correct |
71 ms |
16092 KB |
ok, correct split |
100 |
Correct |
179 ms |
21724 KB |
ok, correct split |
101 |
Correct |
153 ms |
20856 KB |
ok, correct split |
102 |
Correct |
143 ms |
20464 KB |
ok, correct split |
103 |
Correct |
130 ms |
20208 KB |
ok, correct split |
104 |
Correct |
126 ms |
19940 KB |
ok, correct split |
105 |
Correct |
71 ms |
15608 KB |
ok, correct split |
106 |
Correct |
127 ms |
20044 KB |
ok, correct split |
107 |
Correct |
130 ms |
18680 KB |
ok, correct split |
108 |
Correct |
110 ms |
18560 KB |
ok, correct split |
109 |
Correct |
176 ms |
21376 KB |
ok, correct split |
110 |
Correct |
169 ms |
22128 KB |
ok, correct split |
111 |
Correct |
171 ms |
22260 KB |
ok, correct split |
112 |
Correct |
157 ms |
20976 KB |
ok, correct split |
113 |
Correct |
158 ms |
20848 KB |
ok, correct split |
114 |
Correct |
24 ms |
12028 KB |
ok, correct split |
115 |
Correct |
23 ms |
11768 KB |
ok, correct split |
116 |
Correct |
170 ms |
22376 KB |
ok, correct split |
117 |
Correct |
166 ms |
22256 KB |
ok, correct split |
118 |
Correct |
116 ms |
20092 KB |
ok, correct split |
119 |
Correct |
121 ms |
19960 KB |
ok, correct split |
120 |
Correct |
136 ms |
24184 KB |
ok, correct split |
121 |
Correct |
107 ms |
18680 KB |
ok, no valid answer |
122 |
Correct |
109 ms |
18664 KB |
ok, no valid answer |
123 |
Correct |
186 ms |
22052 KB |
ok, no valid answer |
124 |
Correct |
163 ms |
21752 KB |
ok, no valid answer |
125 |
Correct |
103 ms |
19696 KB |
ok, no valid answer |
126 |
Correct |
67 ms |
17648 KB |
ok, no valid answer |
127 |
Correct |
116 ms |
20208 KB |
ok, no valid answer |