# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1032344 | 2024-07-23T15:57:41 Z | 0npata | Fun Tour (APIO20_fun) | C++17 | 26 ms | 608 KB |
#include "fun.h" #include<bits/stdc++.h> using namespace std; #define vec vector const int MXN = 505; vec<int> tree[MXN]; int depth[MXN]; void dfs1(int u, int p = -1) { for(int v : tree[u]) { if(v == p) continue; depth[v] = depth[u]+1; dfs1(v, u); } } void binaryTree(int N, int u, set<int>& used, vec<int>& ans) { int r = u*2+1; int l = u*2; vec<int> right(0); vec<int> left(0); vec<int> nw{l}; while(nw.size() > 0) { int cur = nw.back(); nw.pop_back(); if(used.count(cur) || cur > N) continue; left.push_back(cur); nw.push_back(cur*2); nw.push_back(cur*2+1); } sort(left.begin(), left.end()); nw = {r}; while(nw.size() > 0) { int cur = nw.back(); nw.pop_back(); if(used.count(cur) || cur > N) continue; right.push_back(cur); nw.push_back(cur*2); nw.push_back(cur*2+1); } sort(right.begin(), right.end()); for(int i = 0; i<min(left.size(), right.size()); i++) { ans.push_back(right[i]); ans.push_back(left[i]); used.insert(left[i]); used.insert(right[i]); } ans.push_back(u); if(left.size() > 0) { binaryTree(N, u*2, used, ans); } } std::vector<int> createFunTour(int N, int Q) { if(N>500) { vec<int> res(0); set<int> used{}; binaryTree(N, 1, used, res); for(int i = 0; i<N; i++) res[i]--; return res; } for(int i = 0; i<N; i++) { for(int j = 0; j<N; j++) { if(i == j) { continue; } if(hoursRequired(i, j) == 1) { tree[i].push_back(j); } } } set<int> used; auto comp_depth = [&](int u) { depth[u] = 0; dfs1(u); }; comp_depth(0); int x = 0; for(int i = 0; i<N; i++) { if(depth[i] > depth[x]) x = i; } vec<int> ans(0); for(int i = 0; i<N; i++) { comp_depth(x); for(int i = 0; i<N; i++) { if(!used.count(i) && depth[i] > depth[x]) x = i; } ans.push_back(x); used.insert(x); } assert(used.size() == N); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 448 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 508 KB | Output is correct |
6 | Correct | 1 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 436 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 344 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 456 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 452 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 448 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 508 KB | Output is correct |
6 | Correct | 1 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 436 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 344 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 456 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 452 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 1 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 448 KB | Output is correct |
23 | Correct | 1 ms | 348 KB | Output is correct |
24 | Correct | 14 ms | 504 KB | Output is correct |
25 | Correct | 1 ms | 348 KB | Output is correct |
26 | Correct | 1 ms | 348 KB | Output is correct |
27 | Correct | 2 ms | 456 KB | Output is correct |
28 | Correct | 0 ms | 452 KB | Output is correct |
29 | Correct | 17 ms | 452 KB | Output is correct |
30 | Correct | 1 ms | 348 KB | Output is correct |
31 | Correct | 3 ms | 348 KB | Output is correct |
32 | Correct | 6 ms | 488 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 13 ms | 448 KB | Output is correct |
35 | Correct | 26 ms | 508 KB | Output is correct |
36 | Correct | 26 ms | 344 KB | Output is correct |
37 | Correct | 2 ms | 344 KB | Output is correct |
38 | Correct | 18 ms | 540 KB | Output is correct |
39 | Correct | 8 ms | 484 KB | Output is correct |
40 | Correct | 8 ms | 348 KB | Output is correct |
41 | Correct | 3 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 448 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 508 KB | Output is correct |
5 | Correct | 1 ms | 604 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 436 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 448 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 14 ms | 504 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 2 ms | 456 KB | Output is correct |
16 | Incorrect | 1 ms | 348 KB | Invalid size |
17 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 448 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 452 KB | Output is correct |
8 | Correct | 17 ms | 452 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 3 ms | 348 KB | Output is correct |
11 | Correct | 6 ms | 488 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Incorrect | 1 ms | 608 KB | Invalid size |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 448 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 508 KB | Output is correct |
6 | Correct | 1 ms | 604 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 436 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 344 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 456 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 452 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 1 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 448 KB | Output is correct |
23 | Correct | 1 ms | 348 KB | Output is correct |
24 | Correct | 14 ms | 504 KB | Output is correct |
25 | Correct | 1 ms | 348 KB | Output is correct |
26 | Correct | 1 ms | 348 KB | Output is correct |
27 | Correct | 2 ms | 456 KB | Output is correct |
28 | Correct | 0 ms | 452 KB | Output is correct |
29 | Correct | 17 ms | 452 KB | Output is correct |
30 | Correct | 1 ms | 348 KB | Output is correct |
31 | Correct | 3 ms | 348 KB | Output is correct |
32 | Correct | 6 ms | 488 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 13 ms | 448 KB | Output is correct |
35 | Correct | 26 ms | 508 KB | Output is correct |
36 | Correct | 26 ms | 344 KB | Output is correct |
37 | Correct | 2 ms | 344 KB | Output is correct |
38 | Correct | 18 ms | 540 KB | Output is correct |
39 | Correct | 8 ms | 484 KB | Output is correct |
40 | Correct | 8 ms | 348 KB | Output is correct |
41 | Correct | 3 ms | 348 KB | Output is correct |
42 | Incorrect | 1 ms | 348 KB | Invalid size |
43 | Halted | 0 ms | 0 KB | - |