# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
319557 |
2020-11-05T13:56:28 Z |
VEGAnn |
Fun Tour (APIO20_fun) |
C++14 |
|
5 ms |
5228 KB |
#include "fun.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 100100;
vector<int> g[N], ans, vc[2];
int siz[N], glob, mx;
bool mrk[N];
void dfs(int v, int p, int len){
if (mx < len){
mx = len;
glob = v;
}
for (int u : g[v]){
if (u == p || mrk[u]) continue;
dfs(u, v, len + 1);
}
}
int get(int v, int tp){
for (int it = sz(g[v]) - 1; it >= 0; it--){
int u = g[v][it];
if (mrk[u]) continue;
get(u, tp);
}
vc[tp].PB(v);
}
vector<int> createFunTour(int n, int Q) {
// if (n <= 500){
// for (int i = 0; i < n; i++)
// for (int j = i + 1; j < n; j++){
// int now = hoursRequired(i, j);
//
// if (now == 1){
// g[i].PB(j);
// g[j].PB(i);
// }
// }
// } else
{
// if (n < 10) while (1) {}
for (int i = 1; i < n; i++){
int j = (i - 1) / 2;
// g[i].PB(j);
g[j].PB(i);
}
int rem = n, root = 0;
while (rem > 0){
vc[0].clear();
vc[1].clear();
if (sz(g[root]) > 0 && !mrk[g[root][0]]) get(g[root][0], 0);
if (sz(g[root]) > 1 && !mrk[g[root][1]]) get(g[root][1], 1);
if (sz(vc[0])){
sort(all(vc[0]));
reverse(all(vc[0]));
}
if (sz(vc[1])){
sort(all(vc[1]));
reverse(all(vc[1]));
}
for (int i = 0; i < sz(vc[1]); i++){
ans.PB(vc[0][i]);
ans.PB(vc[1][i]);
mrk[vc[0][i]] = 1;
mrk[vc[1][i]] = 1;
rem -= 2;
}
if (sz(vc[0]) == sz(vc[1])){
rem--;
// assert(rem == 0);
if (rem != 0){
while (1) {}
}
ans.PB(root);
break;
} else {
rem -= 2;
ans.PB(vc[0][sz(vc[1])]);
ans.PB(root);
mrk[vc[0][sz(vc[1])]] = 1;
mrk[root] = 1;
}
if (rem == 0) break;
root = g[root][0];
assert(!mrk[root]);
}
return ans;
}
ans.clear();
mx = -1;
dfs(0, -1, 0);
for (int it = 0; it < n; it++){
ans.PB(glob);
mrk[glob] = 1;
mx = -1;
dfs(glob, -1, 0);
}
return ans;
}
Compilation message
fun.cpp: In function 'int get(int, int)':
fun.cpp:36:1: warning: no return statement in function returning non-void [-Wreturn-type]
36 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
5228 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
5228 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
5228 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
5228 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
5228 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |