IOI 2015 - Towns

#include <bits/stdc++.h>
using namespace std;

// Grader-provided function.
int getDistance(int i, int j);

namespace {

int anchor_v = 0;
int anchor_s = 0;
vector<int> dist_from_v;
vector<int> dist_from_s;
unordered_map<unsigned long long, int> cached_queries;

unsigned long long make_key(int a, int b) {
    if (a > b) swap(a, b);
    return (static_cast<unsigned long long>(a) << 32) ^
           static_cast<unsigned int>(b);
}

int query_distance(int a, int b) {
    if (a == b) return 0;
    if (a == anchor_v) return dist_from_v[b];
    if (b == anchor_v) return dist_from_v[a];
    if (a == anchor_s) return dist_from_s[b];
    if (b == anchor_s) return dist_from_s[a];

    unsigned long long key = make_key(a, b);
    auto it = cached_queries.find(key);
    if (it != cached_queries.end()) return it->second;

    int value = getDistance(a, b);
    cached_queries[key] = value;
    return value;
}

bool same_component(int x, int y, long long pivot) {
    long long shared =
        static_cast<long long>(dist_from_s[x]) + dist_from_s[y] - query_distance(x, y);
    return shared > 2 * pivot;
}

bool has_giant_component(const vector<int> &group, long long pivot, int total_leaves) {
    struct Block {
        int rep;
        int size;
    };

    vector<Block> alive;
    alive.reserve(group.size());
    for (int leaf : group) alive.push_back({leaf, 1});

    vector<Block> dead;
    dead.reserve(group.size());

    while (alive.size() > 1) {
        vector<Block> next;
        next.reserve(alive.size() / 2);

        for (int i = 0; i + 1 < (int)alive.size(); i += 2) {
            const Block &a = alive[i];
            const Block &b = alive[i + 1];
            if (same_component(a.rep, b.rep, pivot)) {
                next.push_back({a.rep, a.size + b.size});
            } else {
                dead.push_back(a);
                dead.push_back(b);
            }
        }
        if (alive.size() % 2 == 1) dead.push_back(alive.back());
        alive.swap(next);
    }

    if (alive.empty()) return false;

    int majority_size = alive[0].size;
    int candidate = alive[0].rep;
    for (const Block &block : dead) {
        if (same_component(candidate, block.rep, pivot)) {
            majority_size += block.size;
        }
    }
    return majority_size > total_leaves / 2;
}

}  // namespace

int hubDistance(int N, int sub) {
    anchor_v = 0;
    dist_from_v.assign(N, 0);
    cached_queries.clear();

    for (int i = 1; i < N; ++i) dist_from_v[i] = getDistance(anchor_v, i);

    anchor_s = 0;
    for (int i = 1; i < N; ++i) {
        if (dist_from_v[i] > dist_from_v[anchor_s]) anchor_s = i;
    }

    dist_from_s.assign(N, 0);
    for (int i = 0; i < N; ++i) {
        if (i == anchor_s) continue;
        dist_from_s[i] = (i == anchor_v ? dist_from_v[anchor_s] : getDistance(anchor_s, i));
    }

    int diameter_endpoint = 0;
    for (int i = 1; i < N; ++i) {
        if (dist_from_s[i] > dist_from_s[diameter_endpoint]) diameter_endpoint = i;
    }
    long long diameter = dist_from_s[diameter_endpoint];
    long long sv_length = dist_from_v[anchor_s];

    vector<long long> projection(N);
    vector<long long> positions;
    positions.reserve(N);
    for (int i = 0; i < N; ++i) {
        projection[i] =
            (static_cast<long long>(dist_from_s[i]) + sv_length - dist_from_v[i]) / 2;
        positions.push_back(projection[i]);
    }

    sort(positions.begin(), positions.end());
    positions.erase(unique(positions.begin(), positions.end()), positions.end());

    long long radius = LLONG_MAX;
    vector<long long> centers;
    for (long long pos : positions) {
        if (pos == 0 || pos == sv_length) continue;
        long long eccentricity = max(pos, diameter - pos);
        if (eccentricity < radius) {
            radius = eccentricity;
            centers.assign(1, pos);
        } else if (eccentricity == radius) {
            centers.push_back(pos);
        }
    }

    if (radius == LLONG_MAX) return 0;
    if (sub <= 2) return static_cast<int>(radius);

    vector<long long> sorted_projection = projection;
    sort(sorted_projection.begin(), sorted_projection.end());
    long long median_left = sorted_projection[(N - 1) / 2];
    long long median_right = sorted_projection[N / 2];

    bool balanced = false;
    for (long long center : centers) {
        if (center < median_left || center > median_right) continue;

        if (median_left != median_right) {
            balanced = true;
            break;
        }

        vector<int> attached_leaves;
        attached_leaves.reserve(N);
        for (int i = 0; i < N; ++i) {
            if (projection[i] == center) attached_leaves.push_back(i);
        }

        if ((int)attached_leaves.size() <= N / 2 ||
            !has_giant_component(attached_leaves, center, N)) {
            balanced = true;
            break;
        }
    }

    return balanced ? static_cast<int>(radius) : -static_cast<int>(radius);
}

int main() {
    // Grader handles interaction.
    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{listings}
\usepackage{xcolor}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{gray},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2015 -- Towns}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
We are given distances only between the $N$ leaves of a weighted tree.
Internal vertices are the large cities.
We must find the hub radius $R$, and for the full task also decide whether some optimal hub is
\emph{balanced}: after deleting it, every remaining component contains at most $N/2$ leaves.

\section{Step 1: Find the Radius}
Pick an arbitrary leaf $v$.
Query all distances from $v$ and let $s$ be the farthest leaf.
Then query all distances from $s$ and let $t$ be the farthest leaf from $s$.
Now $d(s,t)$ is a diameter of the tree.

For any leaf $u$, define
\[
p(u) = \frac{d(u,s) + d(v,s) - d(u,v)}{2}.
\]
This is exactly the distance from $s$ to the branching point where the path from $u$ meets the
path $s \to v$.
Hence the distinct values of $p(u)$ are precisely the vertices on the path $s \to v$ that matter for
the answer.

If a vertex on that path is at distance $x$ from $s$, then its farthest leaf distance is
\[
\max(x,\ d(s,t)-x).
\]
So the center(s) are the internal positions minimizing that value.
There are at most two such positions.

\section{Step 2: A Necessary Median Condition}
Sort the multiset
\[
B = \{\,p(u)\mid u \text{ is a leaf}\,\}.
\]
For a center at position $r$:
\begin{itemize}
  \item leaves with $p(u) < r$ lie in the $s$-side component;
  \item leaves with $p(u) > r$ lie in the $v$-side component;
  \item leaves with $p(u) = r$ branch off exactly at that center.
\end{itemize}

Therefore a balanced hub must satisfy
\[
\#\{p(u) < r\} \le N/2
\quad\text{and}\quad
\#\{p(u) > r\} \le N/2.
\]
Equivalently, $r$ must lie between the two medians of $B$.
If the two medians are different, then any candidate center in that interval is automatically
balanced, because one side already contains exactly $N/2$ leaves, so the group with $p(u)=r$
has size at most $N/2$.

\section{Step 3: Unique-Median Case}
The only nontrivial situation is when both medians are the same value $r$.
Let
\[
X = \{\,u \mid p(u) = r\,\}.
\]
Now we only need to know whether some component of $T-r$ inside this set has more than $N/2$
leaves.

For $x,y \in X$, the editorial observation is:
\[
x,y \text{ are in the same component of } T-r
\iff
d(s,x) + d(s,y) - d(x,y) > 2r.
\]
So $X$ becomes a ``colored balls'' problem:
each component is one color, and we only have an equality test.

We use the standard majority-elimination algorithm:
\begin{itemize}
  \item pair up surviving sets and compare representatives;
  \item merge equal pairs, discard unequal pairs;
  \item if one set survives, verify it against all discarded representatives.
\end{itemize}
This uses fewer than $3|X|/2 \le 3N/2$ extra distance queries.
If no component of $X$ has size $> N/2$, the center is balanced.

\section{Complexity}
\begin{itemize}
  \item \textbf{Queries:} $(N-1) + (N-2)$ to find $s$ and the diameter, plus fewer than
        $3N/2$ in the unique-median case, for a total below $7N/2$.
  \item \textbf{Time:} $O(N \log N)$ because we sort the projection values.
  \item \textbf{Space:} $O(N)$.
\end{itemize}

\section{Implementation}
\begin{lstlisting}
// 1. Query from an arbitrary leaf v, choose the farthest leaf s.
// 2. Query from s, choose the farthest leaf t and get the diameter.
// 3. Compute all projection values p(u) onto the path s -> v.
// 4. Extract the one or two radius-minimizing center positions.
// 5. Filter them using the median condition on B = {p(u)}.
// 6. Only if the median is unique, run majority elimination on leaves with p(u)=r.
\end{lstlisting}

\end{document}