# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
564424 |
2022-05-19T07:49:39 Z |
8e7 |
Fun Tour (APIO20_fun) |
C++17 |
|
270 ms |
22596 KB |
//Challenge: Accepted
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int dis[maxn];
vector<pii> comp[3];
int getsize(int u, int v) {
return attractionsBehind(u, v);
}
int recur[maxn];
int solve(vector<int> v) {
int root = v[0], siz = v.size();
for (int i = 1;i < siz;i++) {
if (getsize(root, v[i]) * 2 > siz) {
root = v[i];
}
}
vector<int> con;
for (int i:v) {
if (i == root) continue;
recur[i] = 0;
dis[i] = hoursRequired(root, i);
if (dis[i] == 1) {
con.push_back(i);
}
}
for (int i = 1;i < con.size();i++) {
for (int j:v) {
if (j != root && !recur[j]) {
//debug(j, con[i], getsize(j, con[i], d));
if (hoursRequired(j, con[i]) < dis[j]) {
recur[j] = i;
}
}
}
}
for (int i = 0;i < con.size();i++) {
for (int j:v) {
if (j != root && recur[j] == i) {
comp[i].push_back({dis[j], j});
}
}
}
return root;
}
vector<int> createFunTour(int N, int Q) {
vector<int> ini, ret;
for (int i = 0;i < N;i++) ini.push_back(i);
int root = solve(ini);
sort(comp, comp + 3, [&] (vector<pii> x, vector<pii> y){return x.size() < y.size();});
for (int i = 0;i < 3;i++) sort(comp[i].begin(), comp[i].end());
if (N == 1) {
ret.push_back(root);
return ret;
}
int cur = 2;
if (comp[0].size() + comp[1].size() >= comp[2].size()) {
if (comp[0].size() && comp[0].back().ff > comp[cur].back().ff) cur = 0;
if (comp[1].size() && comp[1].back().ff > comp[cur].back().ff) cur = 1;
}
for (int i = 0;i < N - 1;i++) {
int pd = comp[cur].back().ff;
ret.push_back(comp[cur].back().ss);
comp[cur].pop_back();
while (cur && comp[cur].size() < comp[cur-1].size()) {
swap(comp[cur], comp[cur-1]);
cur--;
}
auto nxt = [&] (int v1, int v2) {
if (!comp[v1].size()) cur = v2;
else if (!comp[v2].size()) cur = v1;
else if (comp[v1].back().ff > comp[v2].back().ff) cur = v1;
else cur = v2;
};
if (cur == 2) {
nxt(0, 1);
} else {
int c0 = comp[0].size(), c1 = comp[1].size(), c2 = comp[2].size();
if (c0 + c1 < c2) cur = 2;
else if (c0 + c1 == c2) {
if (cur == 0) {
if (c1 && pd < comp[1].back().ff) cur = 1;
else cur = 2;
} else {
if (c0 && pd < comp[0].back().ff) cur = 0;
else cur = 2;
}
} else {
if (cur == 0) nxt(1, 2);
else nxt(0, 2);
}
}
}
ret.push_back(root);
return ret;
}
Compilation message
fun.cpp: In function 'int solve(std::vector<int>)':
fun.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 1;i < con.size();i++) {
| ~~^~~~~~~~~~~~
fun.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0;i < con.size();i++) {
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
312 KB |
Output is correct |
34 |
Correct |
1 ms |
316 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
312 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
126 ms |
16456 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
5 ms |
1236 KB |
Output is correct |
23 |
Correct |
10 ms |
2260 KB |
Output is correct |
24 |
Correct |
15 ms |
3032 KB |
Output is correct |
25 |
Correct |
67 ms |
9432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
9 ms |
1876 KB |
Output is correct |
15 |
Correct |
136 ms |
17348 KB |
Output is correct |
16 |
Correct |
145 ms |
17484 KB |
Output is correct |
17 |
Correct |
23 ms |
4356 KB |
Output is correct |
18 |
Correct |
55 ms |
8004 KB |
Output is correct |
19 |
Correct |
97 ms |
13720 KB |
Output is correct |
20 |
Correct |
4 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
312 KB |
Output is correct |
34 |
Correct |
1 ms |
316 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
312 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
340 KB |
Output is correct |
44 |
Correct |
126 ms |
16456 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
2 ms |
468 KB |
Output is correct |
47 |
Correct |
3 ms |
724 KB |
Output is correct |
48 |
Correct |
5 ms |
1236 KB |
Output is correct |
49 |
Correct |
10 ms |
2260 KB |
Output is correct |
50 |
Correct |
15 ms |
3032 KB |
Output is correct |
51 |
Correct |
67 ms |
9432 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
9 ms |
1876 KB |
Output is correct |
54 |
Correct |
136 ms |
17348 KB |
Output is correct |
55 |
Correct |
145 ms |
17484 KB |
Output is correct |
56 |
Correct |
23 ms |
4356 KB |
Output is correct |
57 |
Correct |
55 ms |
8004 KB |
Output is correct |
58 |
Correct |
97 ms |
13720 KB |
Output is correct |
59 |
Correct |
4 ms |
852 KB |
Output is correct |
60 |
Correct |
148 ms |
17608 KB |
Output is correct |
61 |
Correct |
181 ms |
20096 KB |
Output is correct |
62 |
Correct |
216 ms |
17620 KB |
Output is correct |
63 |
Correct |
171 ms |
21288 KB |
Output is correct |
64 |
Correct |
158 ms |
21440 KB |
Output is correct |
65 |
Correct |
186 ms |
17672 KB |
Output is correct |
66 |
Correct |
270 ms |
19892 KB |
Output is correct |
67 |
Correct |
191 ms |
21528 KB |
Output is correct |
68 |
Correct |
174 ms |
20404 KB |
Output is correct |
69 |
Correct |
261 ms |
22212 KB |
Output is correct |
70 |
Correct |
175 ms |
17404 KB |
Output is correct |
71 |
Correct |
166 ms |
21264 KB |
Output is correct |
72 |
Correct |
181 ms |
20208 KB |
Output is correct |
73 |
Correct |
216 ms |
20356 KB |
Output is correct |
74 |
Correct |
262 ms |
21956 KB |
Output is correct |
75 |
Correct |
156 ms |
17352 KB |
Output is correct |
76 |
Correct |
194 ms |
21564 KB |
Output is correct |
77 |
Correct |
194 ms |
21700 KB |
Output is correct |
78 |
Correct |
179 ms |
20792 KB |
Output is correct |
79 |
Correct |
270 ms |
21816 KB |
Output is correct |
80 |
Correct |
209 ms |
22596 KB |
Output is correct |
81 |
Correct |
173 ms |
17612 KB |
Output is correct |
82 |
Correct |
207 ms |
17360 KB |
Output is correct |
83 |
Correct |
163 ms |
17708 KB |
Output is correct |
84 |
Correct |
71 ms |
7588 KB |
Output is correct |