# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
386127 |
2021-04-05T16:54:33 Z |
phathnv |
Fun Tour (APIO20_fun) |
C++11 |
|
323 ms |
22244 KB |
#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
vector<int> createFunTour(int N, int Q) {
pair<int, int> best = {N, 0};
for(int i = 0; i < N; i++){
int x = attractionsBehind(0, i);
if (x >= (N + 1) / 2)
best = min(best, {x, i});
}
int centroid = best.second;
vector<int> subtreeRoots, distToCentroid(N);
for(int i = 0; i < N; i++){
distToCentroid[i] = hoursRequired(centroid, i);
if (distToCentroid[i] == 1)
subtreeRoots.push_back(i);
}
vector<vector<pair<int, int>>> subtree(3);
for(int i = 0; i < N; i++){
if (i == centroid)
continue;
for(int j = 0; j < (int) subtreeRoots.size(); j++)
if (j + 1 == (int) subtreeRoots.size())
subtree[j].push_back({distToCentroid[i], i});
else if (hoursRequired(subtreeRoots[j], i) == distToCentroid[i] - 1){
subtree[j].push_back({distToCentroid[i], i});
break;
}
}
for(auto &v : subtree)
sort(v.begin(), v.end());
vector<int> answer;
int lastSubtree = -1;
while (true){
int sum = 0, maxSz = -1, big = -1;
pair<int, int> nxt = {-1, -1};
for(int i = 0; i < 3; i++){
sum += subtree[i].size();
if (maxSz < (int) subtree[i].size()){
big = i;
maxSz = subtree[i].size();
}
if (i != lastSubtree && i < (int) subtreeRoots.size())
nxt = max(nxt, {subtree[i].back().first, i});
}
if (sum == 0)
break;
int nxtSubtree = nxt.second;
if (sum <= 2 * maxSz){
vector<int> small;
for(int i = 0; i < 3; i++)
if (i != big)
small.push_back(i);
int cur, szSmall = subtree[small[0]].size() + subtree[small[1]].size(), szBig = subtree[big].size();
if (szSmall != szBig || lastSubtree == -1){
cur = (szBig > szSmall);
} else {
assert(lastSubtree != big);
int othSmall = small[(lastSubtree == small[0])];
if (!subtree[othSmall].empty() && distToCentroid[answer.back()] < subtree[othSmall].back().first){
answer.push_back(subtree[othSmall].back().second);
subtree[othSmall].pop_back();
}
cur = 1;
}
vector<pair<int, int>> part[2];
for(int ind : small)
for(auto p : subtree[ind])
part[0].push_back(p);
sort(part[0].begin(), part[0].end());
part[1] = subtree[big];
while (!part[cur].empty()){
answer.push_back(part[cur].back().second);
part[cur].pop_back();
cur ^= 1;
}
break;
} else {
lastSubtree = nxtSubtree;
answer.push_back(subtree[lastSubtree].back().second);
subtree[lastSubtree].pop_back();
}
}
answer.push_back(centroid);
return answer;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
2 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
2 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
2 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
2 ms |
364 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
2 ms |
364 KB |
Output is correct |
18 |
Correct |
135 ms |
15588 KB |
Output is correct |
19 |
Correct |
2 ms |
364 KB |
Output is correct |
20 |
Correct |
3 ms |
620 KB |
Output is correct |
21 |
Correct |
6 ms |
748 KB |
Output is correct |
22 |
Correct |
7 ms |
1260 KB |
Output is correct |
23 |
Correct |
13 ms |
2284 KB |
Output is correct |
24 |
Correct |
19 ms |
2924 KB |
Output is correct |
25 |
Correct |
75 ms |
9092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
492 KB |
Output is correct |
14 |
Correct |
11 ms |
1772 KB |
Output is correct |
15 |
Correct |
145 ms |
15332 KB |
Output is correct |
16 |
Correct |
150 ms |
15208 KB |
Output is correct |
17 |
Correct |
28 ms |
4076 KB |
Output is correct |
18 |
Correct |
70 ms |
8108 KB |
Output is correct |
19 |
Correct |
119 ms |
12988 KB |
Output is correct |
20 |
Correct |
6 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
2 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
2 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
2 ms |
364 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
1 ms |
364 KB |
Output is correct |
42 |
Correct |
1 ms |
364 KB |
Output is correct |
43 |
Correct |
2 ms |
364 KB |
Output is correct |
44 |
Correct |
135 ms |
15588 KB |
Output is correct |
45 |
Correct |
2 ms |
364 KB |
Output is correct |
46 |
Correct |
3 ms |
620 KB |
Output is correct |
47 |
Correct |
6 ms |
748 KB |
Output is correct |
48 |
Correct |
7 ms |
1260 KB |
Output is correct |
49 |
Correct |
13 ms |
2284 KB |
Output is correct |
50 |
Correct |
19 ms |
2924 KB |
Output is correct |
51 |
Correct |
75 ms |
9092 KB |
Output is correct |
52 |
Correct |
2 ms |
492 KB |
Output is correct |
53 |
Correct |
11 ms |
1772 KB |
Output is correct |
54 |
Correct |
145 ms |
15332 KB |
Output is correct |
55 |
Correct |
150 ms |
15208 KB |
Output is correct |
56 |
Correct |
28 ms |
4076 KB |
Output is correct |
57 |
Correct |
70 ms |
8108 KB |
Output is correct |
58 |
Correct |
119 ms |
12988 KB |
Output is correct |
59 |
Correct |
6 ms |
876 KB |
Output is correct |
60 |
Correct |
190 ms |
17380 KB |
Output is correct |
61 |
Correct |
226 ms |
19684 KB |
Output is correct |
62 |
Correct |
203 ms |
17508 KB |
Output is correct |
63 |
Correct |
222 ms |
21220 KB |
Output is correct |
64 |
Correct |
223 ms |
21136 KB |
Output is correct |
65 |
Correct |
217 ms |
17380 KB |
Output is correct |
66 |
Correct |
256 ms |
19812 KB |
Output is correct |
67 |
Correct |
244 ms |
21260 KB |
Output is correct |
68 |
Correct |
235 ms |
20580 KB |
Output is correct |
69 |
Correct |
323 ms |
21988 KB |
Output is correct |
70 |
Correct |
188 ms |
16868 KB |
Output is correct |
71 |
Correct |
237 ms |
20580 KB |
Output is correct |
72 |
Correct |
306 ms |
19940 KB |
Output is correct |
73 |
Correct |
247 ms |
20452 KB |
Output is correct |
74 |
Correct |
322 ms |
21476 KB |
Output is correct |
75 |
Correct |
214 ms |
17636 KB |
Output is correct |
76 |
Correct |
208 ms |
21476 KB |
Output is correct |
77 |
Correct |
254 ms |
21220 KB |
Output is correct |
78 |
Correct |
266 ms |
20964 KB |
Output is correct |
79 |
Correct |
271 ms |
22000 KB |
Output is correct |
80 |
Correct |
321 ms |
22244 KB |
Output is correct |
81 |
Correct |
216 ms |
16484 KB |
Output is correct |
82 |
Correct |
213 ms |
16868 KB |
Output is correct |
83 |
Correct |
235 ms |
16624 KB |
Output is correct |
84 |
Correct |
79 ms |
7108 KB |
Output is correct |