#include "fun.h"
int N;
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int root,depth[maxn];
int odakle;
vector<int> R,koji[5];
vector<int> V;
bool podub(int a,int b){
return depth[a]<depth[b];
}
void findroot(){
root=1;
for(int i=2;i<=N;i++)
if(attractionsBehind(root-1,i-1)>=(N)/2+1)
root=i;
return;
}
void finddepth(){
for(int i=1;i<=N;i++){
depth[i]=hoursRequired(root-1,i-1);
// cout<<i<<" dubina "<<depth[i]<<endl;
if(depth[i]==1)
R.push_back(i);
}
return;
}
bool insubtree(int a,int b){
//cout<<a<<" "<<b<<" "<<attractionsBehind(a-1,b-1)<<endl;
return attractionsBehind(a-1,b-1)>=(N)/2+1;
}
void findsubtree(){
for(int i=1;i<=N;i++){
if(depth[i]==0)
continue;
if(insubtree(i,R[0]))
koji[0].push_back(i);
else if(insubtree(i,R[1]))
koji[1].push_back(i);
else
koji[2].push_back(i);
}
}
int dist(int a,int b){
return depth[a]+depth[b];
}
void dodaj(int idx){
if(koji[idx].size()==0)
return;
odakle=idx;
//cout<<idx<<" "<<koji[idx].back()<<endl;
V.push_back(koji[idx].back());
koji[idx].pop_back();
//cout<<"DODAJEM "<<idx<<" "<<depth[V.back()]<<endl;
return;
}
void spoj(int a,int b){
//cout<<"SPAJAM "<<a<<" "<<b<<endl;
//cout<<V.size()<<" "<<odakle<<endl;
if(a>b)
swap(a,b);
int c=a^b^3;
if(odakle!=c)
if(dist(V.back(),koji[c].back())<dist(koji[c].back(),koji[3^c^odakle].back()))
dodaj(3^odakle^c);
for(int i=0;i<koji[b].size();i++)
koji[a].push_back(koji[b][i]);
sort(koji[a].begin(),koji[a].end(),podub);
if(odakle==b)
odakle=a;
if(b==1){
koji[1]=koji[2];
if(odakle==2)
odakle=1;
}
koji[2].clear();
//cout<<odakle<<endl;
//cout<<V.size()<<endl;
}
vector<int> createFunTour(int n, int Q) {
N=n;
findroot();
finddepth();
findsubtree();
for(int i=0;i<=2;i++)
if(koji[i].size())
sort(koji[i].begin(),koji[i].end(),podub);
if(koji[2].size()){
if(depth[koji[0].back()]>=depth[koji[1].back()] and depth[koji[0].back()]>=depth[koji[2].back()])
dodaj(0);
else if(depth[koji[1].back()]>=depth[koji[0].back()] and depth[koji[1].back()]>=depth[koji[2].back()])
dodaj(1);
else
dodaj(2);
}
else
if(koji[1].size()>koji[0].size())
dodaj(1);
else
dodaj(0);
while(koji[2].size()){
if(koji[0].size()+koji[1].size()<=koji[2].size()){
spoj(0,1);
break;
}
if(koji[0].size()+koji[2].size()<=koji[1].size()){
spoj(0,2);
break;
}
if(koji[1].size()+koji[2].size()<=koji[0].size()){
spoj(1,2);
break;
}
int nd=0;
if(odakle==0)
nd=1;
for(int i=1;i<=2;i++)
if(depth[koji[i].back()]>depth[koji[nd].back()] and i!=odakle)
nd=i;
dodaj(nd);
}
// cout<<"BBB"<<endl;
//cout<<odakle<<endl;
//cout<<koji[0].size()<<" "<<koji[1].size()<<" "<<koji[2].size()<<endl;
for(int it=1;it<=N;it++)
dodaj(odakle^1);
while(koji[0].size()){
V.push_back(koji[0].back());
koji[0].pop_back();
}
//cout<<"CCC"<<endl;
while(koji[1].size()){
V.push_back(koji[1].back());
koji[1].pop_back();
}
//cout<<"ROOT JE "<<root<<endl;
V.push_back(root);
for(int i=0;i<V.size();i++)
V[i]--;
return V;}
Compilation message
fun.cpp: In function 'void spoj(int, int)':
fun.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<koji[b].size();i++)
| ~^~~~~~~~~~~~~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int i=0;i<V.size();i++)
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
0 ms |
344 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 |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
97 ms |
15208 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
4 ms |
1372 KB |
Output is correct |
23 |
Correct |
10 ms |
2184 KB |
Output is correct |
24 |
Correct |
12 ms |
2904 KB |
Output is correct |
25 |
Correct |
50 ms |
8732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
600 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
7 ms |
1704 KB |
Output is correct |
15 |
Correct |
116 ms |
15196 KB |
Output is correct |
16 |
Correct |
106 ms |
14800 KB |
Output is correct |
17 |
Correct |
17 ms |
3672 KB |
Output is correct |
18 |
Correct |
41 ms |
6976 KB |
Output is correct |
19 |
Correct |
75 ms |
11812 KB |
Output is correct |
20 |
Correct |
3 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
1 ms |
348 KB |
Output is correct |
44 |
Correct |
97 ms |
15208 KB |
Output is correct |
45 |
Correct |
1 ms |
344 KB |
Output is correct |
46 |
Correct |
2 ms |
604 KB |
Output is correct |
47 |
Correct |
2 ms |
604 KB |
Output is correct |
48 |
Correct |
4 ms |
1372 KB |
Output is correct |
49 |
Correct |
10 ms |
2184 KB |
Output is correct |
50 |
Correct |
12 ms |
2904 KB |
Output is correct |
51 |
Correct |
50 ms |
8732 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
7 ms |
1704 KB |
Output is correct |
54 |
Correct |
116 ms |
15196 KB |
Output is correct |
55 |
Correct |
106 ms |
14800 KB |
Output is correct |
56 |
Correct |
17 ms |
3672 KB |
Output is correct |
57 |
Correct |
41 ms |
6976 KB |
Output is correct |
58 |
Correct |
75 ms |
11812 KB |
Output is correct |
59 |
Correct |
3 ms |
860 KB |
Output is correct |
60 |
Correct |
141 ms |
15296 KB |
Output is correct |
61 |
Correct |
141 ms |
17524 KB |
Output is correct |
62 |
Correct |
128 ms |
15308 KB |
Output is correct |
63 |
Correct |
166 ms |
19368 KB |
Output is correct |
64 |
Correct |
136 ms |
18952 KB |
Output is correct |
65 |
Correct |
130 ms |
15392 KB |
Output is correct |
66 |
Correct |
145 ms |
17608 KB |
Output is correct |
67 |
Correct |
149 ms |
19328 KB |
Output is correct |
68 |
Correct |
148 ms |
18540 KB |
Output is correct |
69 |
Correct |
164 ms |
20172 KB |
Output is correct |
70 |
Correct |
123 ms |
15308 KB |
Output is correct |
71 |
Correct |
134 ms |
18888 KB |
Output is correct |
72 |
Correct |
147 ms |
17992 KB |
Output is correct |
73 |
Correct |
138 ms |
18496 KB |
Output is correct |
74 |
Correct |
178 ms |
19760 KB |
Output is correct |
75 |
Correct |
117 ms |
15348 KB |
Output is correct |
76 |
Correct |
133 ms |
19352 KB |
Output is correct |
77 |
Correct |
151 ms |
20464 KB |
Output is correct |
78 |
Correct |
148 ms |
19400 KB |
Output is correct |
79 |
Correct |
194 ms |
21196 KB |
Output is correct |
80 |
Correct |
185 ms |
21196 KB |
Output is correct |
81 |
Correct |
116 ms |
16248 KB |
Output is correct |
82 |
Correct |
123 ms |
16384 KB |
Output is correct |
83 |
Correct |
128 ms |
16508 KB |
Output is correct |
84 |
Correct |
48 ms |
7084 KB |
Output is correct |