#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int dydis = 1e5 + 10;
vector<int> gr[dydis];
int n;
bool rem[dydis] = {};
int dst[dydis] = {};
void dfs(int v, int came) {
if(rem[v]) return;
for(auto x : gr[v]) {
if(x == came) continue;
dst[x] = dst[v] + 1;
////cout << "dst[" << v << "] = " << dst[v] << ", tai dst[" << x << "] = " << dst[x] << endl;
dfs(x, v);
}
}
int furthest (int a) {
// //cout << "ieskau atstumu nuo " << a << endl;
dst[a] = 0;
dfs(a, -1);
int mx = 0; int sk = a;
for(int i = 0; i < n; i++) {
if(rem[i]) continue;
// //cout << "dst[" << i << "] = " << dst[i] << endl;
if(dst[i] > mx) {
mx = dst[i];
sk = i;
}
}
return sk;
}
vector<int> nMazas(){
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if(hoursRequired(i, j) == 1) {
gr[i].push_back(j);
gr[j].push_back(i);
}
}
}
vector<int> ret;
int v = furthest(0);
for(int i = 0; i < n; i++) {
// //cout << "i = " << i << ", v = " << v << endl;
ret.push_back(v);
int was = v;
v = furthest(v);
rem[was] = 1;
// //cout << endl;
}
return ret;
}
pair<int, int> toliausia[dydis];
void d(int v, int came) {
if(rem[v]) return ;
toliausia[v] = {-1, v};
for(auto x : gr[v]) {
if(x == came) continue;
d(x, v);
toliausia[v] = max(toliausia[v], toliausia[x]);
}
toliausia[v].first++;
}
void remN(int v){
int in = v;
while(!rem[v]) {
toliausia[v] = {0, v};
if(v == in) toliausia[v] = {-1, -1};
for(auto x : gr[v]) {
if(x < v) continue;
if(rem[x]) continue;
toliausia[v] = max(toliausia[v], make_pair(toliausia[x].first+1, toliausia[x].second));
}
if(v == 0) break ;
v = (v - 1) / 2;
}
rem[in] = 1;
//cout << "isemus " << in << ", toliausios: \n";
for(int i = 0; i < n; i++) {
//cout << i << "-ajai toliausia yra " << toliausia[i].second << ", ds = "<< toliausia[i].first << endl;
}
}
int findFar(int v) {
pair<int, int> ret = toliausia[v];
int init = v;
int ds = 1;
int V = v;
//cout << "findfar nuo " << v << endl;
while(true) {
for(auto x : gr[v]) {
if(x == init || x < v) continue;
if(rem[x]) continue;
//cout << "v = " << v << ", x = " << x <<", tai dst gali buti " << toliausia[x].first + ds<< endl;
ret = max(ret, make_pair(toliausia[x].first + ds, toliausia[x].second));
}
if(rem[v] || v == 0) break;
init = v;
v = (v - 1) / 2;
ds++;
}
return ret.second;
}
vector<int> createFunTour(int N, int Q) {
n = N;if(n <= 500) return nMazas();
// //cout << "a" << endl;
// if(n <= 500) return nMazas();
for(int i = 1; i < n; i++) {
int pr = (i-1) / 2;
gr[pr].push_back(i);
gr[i].push_back(pr);
}
////cout << "x" << endl;
d(0, -1);
// //cout << "don" << endl;
int v = toliausia[0].second;
set<int> nodes;
for(int i = 0; i < n; i++) nodes.insert(i);
vector<int> ret;
int root = 0;
for(int i = 0; i < n-2; i++) {
int was = v;
v = findFar(v);
//cout << "toliausia nuo " << was << " yra " << v << endl;
remN(was);
ret.push_back(was);
nodes.erase(was);
}
ret.push_back(*nodes.begin());
nodes.erase(*nodes.begin());
ret.push_back(*nodes.begin());
//cout << "ret: "; for(auto x : ret) //cout << x <<" "; //cout << endl;
return ret;
}
Compilation message
fun.cpp: In function 'int findFar(int)':
fun.cpp:99:9: warning: unused variable 'V' [-Wunused-variable]
99 | int V = v;
| ^
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:133:9: warning: unused variable 'root' [-Wunused-variable]
133 | int root = 0;
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2596 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
1 ms |
2644 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2720 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2656 KB |
Output is correct |
19 |
Correct |
2 ms |
2656 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2596 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
1 ms |
2644 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2720 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2656 KB |
Output is correct |
19 |
Correct |
2 ms |
2656 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2644 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
2 ms |
2644 KB |
Output is correct |
24 |
Correct |
11 ms |
2708 KB |
Output is correct |
25 |
Correct |
2 ms |
2644 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
13 ms |
2720 KB |
Output is correct |
30 |
Correct |
1 ms |
2644 KB |
Output is correct |
31 |
Correct |
3 ms |
2656 KB |
Output is correct |
32 |
Correct |
4 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
12 ms |
2752 KB |
Output is correct |
35 |
Correct |
13 ms |
2660 KB |
Output is correct |
36 |
Correct |
13 ms |
2656 KB |
Output is correct |
37 |
Correct |
3 ms |
2644 KB |
Output is correct |
38 |
Correct |
16 ms |
2644 KB |
Output is correct |
39 |
Correct |
5 ms |
2644 KB |
Output is correct |
40 |
Correct |
7 ms |
2644 KB |
Output is correct |
41 |
Correct |
3 ms |
2644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2596 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
11 ms |
2708 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
136 ms |
24256 KB |
Output is correct |
19 |
Correct |
2 ms |
2772 KB |
Output is correct |
20 |
Correct |
4 ms |
3028 KB |
Output is correct |
21 |
Correct |
6 ms |
3156 KB |
Output is correct |
22 |
Correct |
13 ms |
4060 KB |
Output is correct |
23 |
Correct |
15 ms |
5460 KB |
Output is correct |
24 |
Correct |
20 ms |
6356 KB |
Output is correct |
25 |
Correct |
74 ms |
15076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2596 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
13 ms |
2720 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
3 ms |
2656 KB |
Output is correct |
11 |
Correct |
4 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Incorrect |
3 ms |
2772 KB |
Tour is not fun |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2596 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
1 ms |
2644 KB |
Output is correct |
15 |
Correct |
1 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2720 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2656 KB |
Output is correct |
19 |
Correct |
2 ms |
2656 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2644 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
2 ms |
2644 KB |
Output is correct |
24 |
Correct |
11 ms |
2708 KB |
Output is correct |
25 |
Correct |
2 ms |
2644 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
13 ms |
2720 KB |
Output is correct |
30 |
Correct |
1 ms |
2644 KB |
Output is correct |
31 |
Correct |
3 ms |
2656 KB |
Output is correct |
32 |
Correct |
4 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
12 ms |
2752 KB |
Output is correct |
35 |
Correct |
13 ms |
2660 KB |
Output is correct |
36 |
Correct |
13 ms |
2656 KB |
Output is correct |
37 |
Correct |
3 ms |
2644 KB |
Output is correct |
38 |
Correct |
16 ms |
2644 KB |
Output is correct |
39 |
Correct |
5 ms |
2644 KB |
Output is correct |
40 |
Correct |
7 ms |
2644 KB |
Output is correct |
41 |
Correct |
3 ms |
2644 KB |
Output is correct |
42 |
Correct |
2 ms |
2644 KB |
Output is correct |
43 |
Correct |
2 ms |
2644 KB |
Output is correct |
44 |
Correct |
136 ms |
24256 KB |
Output is correct |
45 |
Correct |
2 ms |
2772 KB |
Output is correct |
46 |
Correct |
4 ms |
3028 KB |
Output is correct |
47 |
Correct |
6 ms |
3156 KB |
Output is correct |
48 |
Correct |
13 ms |
4060 KB |
Output is correct |
49 |
Correct |
15 ms |
5460 KB |
Output is correct |
50 |
Correct |
20 ms |
6356 KB |
Output is correct |
51 |
Correct |
74 ms |
15076 KB |
Output is correct |
52 |
Incorrect |
3 ms |
2772 KB |
Tour is not fun |
53 |
Halted |
0 ms |
0 KB |
- |