#include "fun.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> dist, adj, ans;
vector<pair<int, int> > child[4];
vector<int> createFunTour(int n, int q){
adj.clear(); dist.clear(); ans.clear();
for(int i = 0; i < 4; i ++) child[i].clear();
int rt = 0, cent = 0, mx_sz = n + 5;
for(int i = 1; i < n; i ++){
int w = attractionsBehind(rt, i);
if(w >= (n + 1) / 2 && w < mx_sz){
cent = i; mx_sz = w;
}
}
rt = cent;
dist.resize(n);
for(int i = 0; i < n; i ++){
if(i == rt) dist[i] = 0;
else dist[i] = hoursRequired(i, rt);
if(dist[i] == 1) adj.push_back(i);
}
for(int i = 0; i < n; i ++) if(i != rt){
bool ok = 0;
for(int j = 1; j < adj.size(); j ++)
if(dist[i] == hoursRequired(adj[j], i) + 1){
child[j].push_back({dist[i], i});
ok = 1; break;
}
if(!ok)
child[0].push_back({dist[i], i});
}
int mn = 0;
for(int i = 1; i < 3; i ++)
if(child[i].size() < child[mn].size())
mn = i;
child[mn].push_back({dist[rt], rt});
for(int i = 0; i < adj.size(); i ++)
sort(child[i].begin(), child[i].end());
int last = -1, cnt = n;
for(; cnt > 0;){
if(max(child[0].size(), max(child[1].size(), child[2].size())) * 2 == cnt)
break;
int nw = -1;
for(int i = 0; i < 3; i ++) if(i != last && child[i].size()){
if(nw == -1 || child[nw].back().first < child[i].back().first)
nw = i;
}
ans.push_back(child[nw].back().second);
child[nw].pop_back(); last = nw;
cnt --;
}
if(child[0].size() < child[1].size()){
swap(child[0], child[1]);
if(last == 0) last = 1;
else if(last == 1) last = 0;
}
if(child[0].size() < child[2].size()){
swap(child[0], child[2]);
if(last == 0) last = 2;
else if(last == 2) last = 0;
}
if(child[1].size() < child[2].size()){
swap(child[1], child[2]);
if(last == 1) last = 2;
else if(last == 2) last = 1;
}
if(child[2].size() && child[2].back().first > child[1].back().first){
swap(child[1], child[2]);
if(last == 1) last = 2;
else if(last == 2) last = 1;
}
if(child[1].size() && (last == 0 || (last == 2 && child[1].back().first > child[0].back().first))){
ans.push_back(child[1].back().second);
child[1].pop_back(); cnt --;
last = 1;
}
while(cnt){
if(child[0].size()){
ans.push_back(child[0].back().second);
child[0].pop_back(); cnt --;
}
if(child[1].empty() && child[2].empty()) continue;
if(child[1].empty()){
ans.push_back(child[2].back().second);
child[2].pop_back(); cnt --;
continue;
}
if(child[2].empty()){
ans.push_back(child[1].back().second);
child[1].pop_back(); cnt --;
continue;
}
if(child[1].back().first < child[2].back().first)
swap(child[1], child[2]);
ans.push_back(child[1].back().second);
child[1].pop_back(); cnt --;
}
return ans;
}
Compilation message
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int j = 1; j < adj.size(); j ++)
| ~~^~~~~~~~~~~~
fun.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i = 0; i < adj.size(); i ++)
| ~~^~~~~~~~~~~~
fun.cpp:52:70: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
52 | if(max(child[0].size(), max(child[1].size(), child[2].size())) * 2 == cnt)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
288 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
292 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
288 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
292 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
292 KB |
Output is correct |
21 |
Correct |
1 ms |
288 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
292 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 ms |
288 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
292 KB |
Output is correct |
36 |
Correct |
1 ms |
288 KB |
Output is correct |
37 |
Correct |
1 ms |
292 KB |
Output is correct |
38 |
Correct |
1 ms |
268 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
292 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
288 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
138 ms |
16832 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
460 KB |
Output is correct |
21 |
Correct |
4 ms |
716 KB |
Output is correct |
22 |
Correct |
7 ms |
1228 KB |
Output is correct |
23 |
Correct |
14 ms |
2380 KB |
Output is correct |
24 |
Correct |
18 ms |
3020 KB |
Output is correct |
25 |
Correct |
82 ms |
9692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
292 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
292 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
288 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
10 ms |
1740 KB |
Output is correct |
15 |
Correct |
150 ms |
16448 KB |
Output is correct |
16 |
Correct |
144 ms |
16320 KB |
Output is correct |
17 |
Correct |
25 ms |
4152 KB |
Output is correct |
18 |
Correct |
63 ms |
7620 KB |
Output is correct |
19 |
Correct |
118 ms |
13168 KB |
Output is correct |
20 |
Correct |
5 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
288 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
292 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
292 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
292 KB |
Output is correct |
21 |
Correct |
1 ms |
288 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
292 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
1 ms |
288 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
292 KB |
Output is correct |
36 |
Correct |
1 ms |
288 KB |
Output is correct |
37 |
Correct |
1 ms |
292 KB |
Output is correct |
38 |
Correct |
1 ms |
268 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
1 ms |
332 KB |
Output is correct |
43 |
Correct |
1 ms |
332 KB |
Output is correct |
44 |
Correct |
138 ms |
16832 KB |
Output is correct |
45 |
Correct |
1 ms |
332 KB |
Output is correct |
46 |
Correct |
2 ms |
460 KB |
Output is correct |
47 |
Correct |
4 ms |
716 KB |
Output is correct |
48 |
Correct |
7 ms |
1228 KB |
Output is correct |
49 |
Correct |
14 ms |
2380 KB |
Output is correct |
50 |
Correct |
18 ms |
3020 KB |
Output is correct |
51 |
Correct |
82 ms |
9692 KB |
Output is correct |
52 |
Correct |
1 ms |
332 KB |
Output is correct |
53 |
Correct |
10 ms |
1740 KB |
Output is correct |
54 |
Correct |
150 ms |
16448 KB |
Output is correct |
55 |
Correct |
144 ms |
16320 KB |
Output is correct |
56 |
Correct |
25 ms |
4152 KB |
Output is correct |
57 |
Correct |
63 ms |
7620 KB |
Output is correct |
58 |
Correct |
118 ms |
13168 KB |
Output is correct |
59 |
Correct |
5 ms |
844 KB |
Output is correct |
60 |
Correct |
186 ms |
16548 KB |
Output is correct |
61 |
Correct |
206 ms |
19116 KB |
Output is correct |
62 |
Correct |
176 ms |
16560 KB |
Output is correct |
63 |
Correct |
199 ms |
20536 KB |
Output is correct |
64 |
Correct |
203 ms |
20456 KB |
Output is correct |
65 |
Correct |
213 ms |
16776 KB |
Output is correct |
66 |
Correct |
231 ms |
18964 KB |
Output is correct |
67 |
Correct |
244 ms |
20456 KB |
Output is correct |
68 |
Correct |
246 ms |
19856 KB |
Output is correct |
69 |
Correct |
274 ms |
21216 KB |
Output is correct |
70 |
Correct |
187 ms |
16900 KB |
Output is correct |
71 |
Correct |
211 ms |
20668 KB |
Output is correct |
72 |
Correct |
224 ms |
19152 KB |
Output is correct |
73 |
Correct |
237 ms |
19580 KB |
Output is correct |
74 |
Correct |
255 ms |
21344 KB |
Output is correct |
75 |
Correct |
219 ms |
16828 KB |
Output is correct |
76 |
Correct |
222 ms |
20576 KB |
Output is correct |
77 |
Correct |
245 ms |
20540 KB |
Output is correct |
78 |
Correct |
260 ms |
19996 KB |
Output is correct |
79 |
Correct |
309 ms |
21212 KB |
Output is correct |
80 |
Correct |
307 ms |
21408 KB |
Output is correct |
81 |
Correct |
186 ms |
16444 KB |
Output is correct |
82 |
Correct |
213 ms |
16984 KB |
Output is correct |
83 |
Correct |
204 ms |
16536 KB |
Output is correct |
84 |
Correct |
83 ms |
7120 KB |
Output is correct |