/**
* [S1-3] Let d(u,v) be the dist from station u to station v.
* Obs1: d(.,.) is a norm.
* We know dist(u,v) = dist(v,u) and dist(a,b) + dist(b,c) >= dist(a,c). This
* means we can pre-compute the dist between every pair of nodes.
* Obs2: For every u, d(u,v) (v != u) achieves the min => v and u are different
* types of station. v is the first station we can get to after leaving u.
* For simplicity, we define v to be u's "conjugate" iff d(u,v) achieves
* the minimum over all v. It is easy to see that every node has a unique
* conjugate.
* These observations lead us to a recursive solution. Find a conjugate pair
* (u,v) with no other stations between them. (A pair always exists~) d(u,v) is
* their difference in block number. The pair splits the railway line into two
* parts - a left and a right part. We can determine which part a station w
* belongs to by finding which one of d(w,u), d(w,v) is smaller. Assign u, v to
* their corresponding part and recursively solve them would be good.
*
* Calls needed: n * (n - 1) / 2
* Implementation 1 (Solves [S1-3] (bound tight)
*/
#include <bits/stdc++.h>
#include "rail.h"
typedef std::vector<int> vec;
const int INF = 0x3f3f3f3f;
std::vector<vec> dist;
int* location; // location of the stations, ans variable
int* s_type; // station type, ans variable
inline void set_conj(int s, int t) {
s_type[t] = 3 - s_type[s];
location[t] = (s_type[s] == 1 ? 1 : -1) * dist[s][t] + location[s];
}
void solve(vec nodes, int ref) {
if (int(nodes.size()) == 1)
return;
int r1 = -1, r2 = -1, min_dist = INF;
for (int k : nodes) {
if (k != ref && dist[k][ref] < min_dist)
min_dist = dist[k][ref], r1 = k;
}
set_conj(ref, r1);
min_dist = INF;
for (int k : nodes) {
if (k != r1 && dist[k][r1] < min_dist)
min_dist = dist[k][r1], r2 = k;
}
set_conj(r1, r2);
vec part1 = {r1}, part2 = {r2};
for (int k : nodes) {
if (k == r1 || k == r2 || s_type[k] != 0)
continue;
if (dist[k][r1] <= min_dist)
set_conj(r1, k);
else if (dist[k][r2] <= min_dist)
set_conj(r2, k);
else if (dist[k][r1] < dist[k][r2])
part1.push_back(k);
else
part2.push_back(k);
}
solve(part1, r1);
solve(part2, r2);
}
void findLocation(int n, int first, int _location[], int _s_type[]) {
location = _location, s_type = _s_type;
memset(s_type, 0, sizeof(int) * n);
dist.assign(n, vec(n, 0));
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++)
dist[i][j] = dist[j][i] = getDistance(i, j);
}
vec all_nodes(n);
for (int i = 0; i < n; i++)
all_nodes[i] = i;
location[0] = first, s_type[0] = 1;
solve(all_nodes, 0);
}
