# APIO 2020 Problems and Solutions – Fun Tour

## Problem :

There are NN attractions in the biggest theme park in Jakarta, numbered from 00 to N - 1N−1. These attractions are connected by N - 1N−1 bidirectional roads such that there is a unique path between any pair of attractions through the roads. The roads are numbered from 00 to N - 2N−2. The ii-th road connects the A[i]A[i]-th attraction and the B[i]B[i]-th attraction and takes one hour to walk through. To avoid congestion, each attraction is an endpoint of at most three roads.

You would like to create a tour visiting all attractions exactly once. Going through many roads when going from an attraction to another is boring. To create a fun tour, you would like to find an ordering of all attractions, such that the time required to visit the next attraction is not longer than the time required to visit the previous attraction. In other words, you would like to find a sequence P[0], P[1], \ldots, P[N-1]P[0],P[1],…,P[N−1] containing all integers from 00 to N - 1N−1 exactly once such that the time required to go from the P[i]P[i]-th attraction to the P[i+1]P[i+1]-th attraction is not longer than the time required to go from the P[i-1]P[i−1]-th attraction to the P[i]P[i]-th attraction, for 0 \lt i \lt N - 10<i<N−1.

You do not have the complete map of the attractions. Therefore, you have to ask several questions to the information centre to create a fun tour. You can ask at most QQ questions, each with two parameters XX and YY, where 0 \le X, Y \lt N0≤X,Y<N. Each question is either of the following:

• How many hours are required to go from the XX-th attraction to the YY-th attraction? In particular, if X = YX=Y, the answer is 00.
• How many attractions ZZ such that you have to visit the YY-th attraction to go from the XX-th attraction to the ZZ-th attraction? The YY-th attraction will be counted as well. In particular, if X = YX=Y, the answer is NN.

You have to implement createFunTour function:

• createFunTour(N, Q) – This function will be called by the grader exactly once.
• NN: An integer representing the number of attractions.
• QQ: An integer representing the maximum number of questions.
• This function is allowed to call two grader functions:
• hoursRequired(X, Y)
• XX: An integer representing the first attraction.
• YY: An integer representing the second attraction.
• This function returns an integer representing hours required to go from the XX-th attraction to the YY-th attraction.
• If either XX or YY is not an integer between 00 and N - 1N−1, then you will get a WA verdict.
• attractionsBehind(X, Y)
• XX: An integer representing the first attraction.
• YY: An integer representing the second attraction.
• This function returns an integer representing the number of attractions ZZ such that you have to visit the YY-th attraction to go from the XX-th attraction to the ZZ-th attraction.
• If either XX or YY is not an integer between 00 and N - 1N−1, then you will get a WA verdict.
• This function must return an array of NN integers representing the permutation of attractions in a fun tour.

### Example :

In the following example, N = 7N=7, Q = 400\,000Q=400000, A = [0, 0, 0, 1, 1, 2]A=[0,0,0,1,1,2], and B = [1, 5, 6, 2, 4, 3]B=[1,5,6,2,4,3]. The example is illustrated by the following image:

Grader will call createFunTour(7, 400000).

• If the contestant queries hoursRequired(3, 5), then the function will return 44.
• If the contestant queries hoursRequired(5, 4), then the function will return 33.
• If the contestant queries attractionsBehind(5, 1), then the function will return 44. To go from the fifth attraction to the first, second, third, and fourth attractions, you will have to visit the first attraction.
• If the contestant queries attractionsBehind(1, 5), then the function will return 11.
• The contestant can return [3, 6, 4, 5, 2, 0, 1][3,6,4,5,2,0,1] since the hours required to visit the next attractions are [4, 3, 3, 3, 2, 1][4,3,3,3,2,1] in order.

### Constraints :

• 2 \le N \le 100\,0002≤N≤100000.
• Q = 400\,000Q=400000.
• It is possible to travel between any pair of attractions through the roads.
• Each attraction is an endpoint of at most three roads.

### Subtask 1 (10 points) :

• N \le 17N≤17.

### Subtask 2 (16 points) :

• N \le 500N≤500.

### Subtask 3 (21 points) :

• There is a road connecting the ii-th attraction and the \left\lfloor\frac{i - 1}{2} \right\rfloor⌊2i−1​⌋-th attraction, for all 1 \le i \lt N1≤i<N.

### Subtask 4 (19 points) :

• There is at least an attraction TT such that for all 0 \le i \lt N0≤i<NhoursRequired(T, i) \lt 30<30 and there exists an interval [L[i], R[i]][L[i],R[i]] (0 \le L[i] \le i \le R[i] \lt N0≤L[i]≤i≤R[i]<N) satisfying the following conditions:
• You have to visit the ii-th attraction to go from the TT-th attraction to the jj-th attraction if and only if L[i] \le j \le R[i]L[i]≤j≤R[i].
• If L[i] \lt iL[i]<i, then there must be exactly one attraction XX such that:
• L[i] \le X \lt iL[i]≤X<i.
• There is a road connecting the ii-th attraction and the XX-th attraction.
• If i \lt R[i]i<R[i], then there must be exactly one attraction YY such that:
• i \lt Y \le R[i]i<Y≤R[i].
• There is a road connecting the ii-th attraction and the YY-th attraction.

### Subtask 5 (34 points) :

N Q
A[0] B[0]
A[1] B[1]
.
.
.
A[N-2] B[N-2]


The sample grader writes the integers returned by createFunTour if it correctly returns an array of NN integers representing the permutation of attractions in a fun tour and calls both hoursRequired and attractionsBehind not more than QQ times combined. Otherwise, it prints a wrong answer message.

## Solution :

#include "fun.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 505;
const int mod = 1e9 + 7;

vector<int> createFunTour(int N, int Q) {
int n = N;
vector<int> dist(n);
pi dap(1e9, 1e9);
for(int i=0; i<n; i++){
int foo = attractionsBehind(0, i);
if(2 * foo > n){
dap = min(dap, pi(foo, i));
}
}
int C = dap.second;
for(int i=0; i<n; i++){
dist[i] = hoursRequired(C, i);
}
vector<int> sons[3];
for(int i=0; i<n; i++){
if(i == C) continue;
int put = 0;
if(hoursRequired(adj[j], i) == dist[i] - 1){
put = j;
break;
}
}
sons[put].push_back(i);
}
sort(all(sons[i]), [&](const int &a, const int &b){
return dist[a] < dist[b];
});
}
vector<int> ans;
auto majority = [&](){
int sum = sz(sons[0]) + sz(sons[1]) + sz(sons[2]);
for(int i=0; i<3; i++){
if(sz(sons[i]) * 2 >= sum) return i;
}
return -1;
};
int prv = -1;
if(majority() == -1){
while(true){
vector<int> v;
assert(sz(sons[j]));
v.push_back(j);
}
sort(all(v), [&](const int &a, const int &b){
int da = dist[sons[a].back()];
int db = dist[sons[b].back()];
if(da != db) return da > db;
return (a != prv) > (b != prv);
});
if(v[0] == prv) prv = v[1];
else prv = v[0];
assert(sz(sons[prv]));
ans.push_back(sons[prv].back());
sons[prv].pop_back();
if(prv == v[0] && majority() != -1) break;
}
}
int foo = sz(ans);
int w = majority();
vector<pi> x, y;
for(int i=0; i<3; i++){
for(auto &j : sons[i]){
if(i == w) x.emplace_back(j, i);
else y.emplace_back(j, i);
}
}
auto cmp = [&](const pi &a, const pi &b){
if(dist[a.first] != dist[b.first]){
return dist[a.first] > dist[b.first];
}
return (a.second != prv) < (b.second != prv);
};
assert(abs(sz(x) - sz(y)) <= 1);
sort(all(x), cmp);
sort(all(y), cmp);
if(sz(x) && sz(y) && x[0].first < y[0].first) swap(x, y);
if(sz(x) && x[0].second == prv) swap(x, y);
if(sz(x) <= sz(y)) x.emplace_back(C, -1);
else y.emplace_back(C, -1);
for(int i=0; i<sz(x); i++){
ans.push_back(x[i].first);
if(i < sz(y)) ans.push_back(y[i].first);
}
/*
for(int i=2; i<sz(ans); i++){
if(hoursRequired(ans[i-2], ans[i-1]) < hoursRequired(ans[i-1], ans[i])){
puts("---");
cout << foo << endl;
for(auto &j : ans) printf("%d " , j);
puts("");
}
}*/
return ans;
}

491 total views,  1 views today