IOI 2017 - Simurgh

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

int count_common_roads(vector<int> &r);

namespace {

struct Solver {
    int n, m;
    vector<int> U, V;
    vector<vector<int>> adj;
    vector<int> tin, low, comp_id;
    vector<char> is_bridge;
    int timer = 0;
    vector<int> status;
    vector<vector<int>> comp_edges;
    vector<vector<int>> comp_vertices;
    vector<char> in_sub;
    struct Ear {
        int a = -1;
        int b = -1;
        vector<int> edges;
    };

    int other(int eid, int x) const { return U[eid] ^ V[eid] ^ x; }

    void bridge_dfs(int v, int peid) {
        tin[v] = low[v] = timer++;
        for (int eid : adj[v]) {
            if (eid == peid) continue;
            int to = other(eid, v);
            if (tin[to] != -1) {
                low[v] = min(low[v], tin[to]);
            } else {
                bridge_dfs(to, eid);
                low[v] = min(low[v], low[to]);
                if (low[to] > tin[v]) is_bridge[eid] = 1;
            }
        }
    }

    void build_components() {
        tin.assign(n, -1);
        low.assign(n, 0);
        is_bridge.assign(m, 0);
        bridge_dfs(0, -1);

        status.assign(m, -1);
        for (int eid = 0; eid < m; ++eid) {
            if (is_bridge[eid]) status[eid] = 1;
        }

        comp_id.assign(n, -1);
        int comps = 0;
        for (int s = 0; s < n; ++s) {
            if (comp_id[s] != -1) continue;
            queue<int> q;
            q.push(s);
            comp_id[s] = comps;
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (int eid : adj[v]) {
                    if (is_bridge[eid]) continue;
                    int to = other(eid, v);
                    if (comp_id[to] == -1) {
                        comp_id[to] = comps;
                        q.push(to);
                    }
                }
            }
            ++comps;
        }

        comp_edges.assign(comps, {});
        comp_vertices.assign(comps, {});
        for (int v = 0; v < n; ++v) comp_vertices[comp_id[v]].push_back(v);
        for (int eid = 0; eid < m; ++eid) {
            if (is_bridge[eid]) continue;
            comp_edges[comp_id[U[eid]]].push_back(eid);
        }
    }

    vector<int> build_query_tree(const vector<int> &cycle_edges, int omit) {
        vector<char> blocked(m, 0), seen(n, 0);
        for (int eid : cycle_edges) blocked[eid] = 1;

        queue<int> q;
        for (int eid : cycle_edges) {
            if (!seen[U[eid]]) {
                seen[U[eid]] = 1;
                q.push(U[eid]);
            }
            if (!seen[V[eid]]) {
                seen[V[eid]] = 1;
                q.push(V[eid]);
            }
        }

        vector<int> tree_edges;
        tree_edges.reserve(n - 1);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int eid : adj[v]) {
                if (blocked[eid]) continue;
                int to = other(eid, v);
                if (!seen[to]) {
                    seen[to] = 1;
                    q.push(to);
                    tree_edges.push_back(eid);
                }
            }
        }

        for (int eid : cycle_edges) {
            if (eid != omit) tree_edges.push_back(eid);
        }
        return tree_edges;
    }

    vector<int> path_without_edge(int start, int goal, int banned, int cid) {
        vector<int> parent_v(n, -1), parent_e(n, -1);
        queue<int> q;
        q.push(start);
        parent_v[start] = start;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (v == goal) break;
            for (int eid : adj[v]) {
                if (eid == banned || is_bridge[eid]) continue;
                if (comp_id[other(eid, v)] != cid) continue;
                int to = other(eid, v);
                if (parent_v[to] != -1) continue;
                parent_v[to] = v;
                parent_e[to] = eid;
                q.push(to);
            }
        }

        vector<int> path;
        int cur = goal;
        while (cur != start) {
            path.push_back(parent_e[cur]);
            cur = parent_v[cur];
        }
        reverse(path.begin(), path.end());
        return path;
    }

    void classify_initial_cycle(const vector<int> &cycle) {
        vector<int> values(cycle.size());
        int best = -1;
        for (int i = 0; i < (int)cycle.size(); ++i) {
            vector<int> tree = build_query_tree(cycle, cycle[i]);
            values[i] = count_common_roads(tree);
            best = max(best, values[i]);
        }
        for (int i = 0; i < (int)cycle.size(); ++i) {
            status[cycle[i]] = (values[i] < best ? 1 : 0);
        }
    }

    vector<int> known_path(int src, int dst, int cid) {
        vector<int> parent_v(n, -1), parent_e(n, -1);
        queue<int> q;
        q.push(src);
        parent_v[src] = src;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (v == dst) break;
            for (int eid : adj[v]) {
                if (is_bridge[eid] || status[eid] == -1) continue;
                if (comp_id[other(eid, v)] != cid) continue;
                int to = other(eid, v);
                if (parent_v[to] != -1) continue;
                parent_v[to] = v;
                parent_e[to] = eid;
                q.push(to);
            }
        }

        vector<int> path;
        int cur = dst;
        while (cur != src) {
            path.push_back(parent_e[cur]);
            cur = parent_v[cur];
        }
        reverse(path.begin(), path.end());
        return path;
    }

    vector<int> reconstruct_to_source(int v, const vector<int> &par_v,
                                      const vector<int> &par_e, int source) {
        vector<int> path;
        while (v != source) {
            path.push_back(par_e[v]);
            v = par_v[v];
        }
        return path;
    }

    Ear find_ear(int cid) {
        vector<int> source(n, -1), par_v(n, -1), par_e(n, -1);
        queue<int> q;
        for (int v : comp_vertices[cid]) {
            if (in_sub[v]) {
                source[v] = v;
                q.push(v);
            }
        }

        auto build = [&](int end_a, int end_b, int meet_u, int meet_v, int bridge_e) {
            vector<int> left = reconstruct_to_source(meet_u, par_v, par_e, end_a);
            reverse(left.begin(), left.end());
            vector<int> right = reconstruct_to_source(meet_v, par_v, par_e, end_b);
            vector<int> ear = left;
            if (bridge_e != -1) ear.push_back(bridge_e);
            ear.insert(ear.end(), right.begin(), right.end());
            return Ear{end_a, end_b, ear};
        };

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int eid : adj[v]) {
                if (is_bridge[eid] || status[eid] != -1) continue;
                int to = other(eid, v);
                if (comp_id[to] != cid) continue;

                if (in_sub[v] && in_sub[to] && source[v] != source[to]) {
                    return Ear{v, to, {eid}};
                }

                if (!in_sub[to]) {
                    if (source[to] == -1) {
                        source[to] = source[v];
                        par_v[to] = v;
                        par_e[to] = eid;
                        q.push(to);
                    } else if (source[to] != source[v]) {
                        int s1 = source[v];
                        int s2 = source[to];
                        return build(s1, s2, v, to, eid);
                    } else if (par_v[v] != to && par_v[to] != v) {
                        int s = source[v];
                        return build(s, s, v, to, eid);
                    }
                } else if (source[v] != to) {
                    int s1 = source[v];
                    int s2 = to;
                    return build(s1, s2, v, to, eid);
                } else if (!in_sub[v] && par_v[v] != to) {
                    int s = source[v];
                    return build(s, s, v, v, eid);
                }
            }
        }
        return Ear{};
    }

    void classify_ear(const Ear &ear, int cid) {
        int a = ear.a;
        int b = ear.b;
        vector<int> q_path = known_path(a, b, cid);
        vector<int> cycle = q_path;
        cycle.insert(cycle.end(), ear.edges.begin(), ear.edges.end());

        int baseline_nonroyal = -1;
        for (int eid : q_path) {
            if (status[eid] == 0) {
                baseline_nonroyal = eid;
                break;
            }
        }

        if (baseline_nonroyal != -1) {
            vector<int> base_tree = build_query_tree(cycle, baseline_nonroyal);
            int base = count_common_roads(base_tree);
            for (int eid : ear.edges) {
                vector<int> tree = build_query_tree(cycle, eid);
                int val = count_common_roads(tree);
                status[eid] = (val < base ? 1 : 0);
            }
        } else {
            vector<int> values(ear.edges.size());
            int best = -1;
            for (int i = 0; i < (int)ear.edges.size(); ++i) {
                vector<int> tree = build_query_tree(cycle, ear.edges[i]);
                values[i] = count_common_roads(tree);
                best = max(best, values[i]);
            }
            for (int i = 0; i < (int)ear.edges.size(); ++i) {
                status[ear.edges[i]] = (values[i] < best ? 1 : 0);
            }
        }

        for (int eid : ear.edges) {
            in_sub[U[eid]] = 1;
            in_sub[V[eid]] = 1;
        }
    }

    vector<int> solve_component(int cid) {
        if (comp_edges[cid].empty()) return {};

        in_sub.assign(n, 0);
        int first = comp_edges[cid][0];
        vector<int> cycle = path_without_edge(U[first], V[first], first, cid);
        cycle.push_back(first);
        classify_initial_cycle(cycle);
        for (int eid : cycle) {
            in_sub[U[eid]] = 1;
            in_sub[V[eid]] = 1;
        }

        while (true) {
            bool done = true;
            for (int eid : comp_edges[cid]) {
                if (status[eid] == -1) {
                    done = false;
                    break;
                }
            }
            if (done) break;
            Ear ear = find_ear(cid);
            if (ear.edges.empty()) break;
            classify_ear(ear, cid);
        }

        vector<int> royal;
        for (int eid : comp_edges[cid]) {
            if (status[eid] == 1) royal.push_back(eid);
        }
        return royal;
    }

    vector<int> run() {
        build_components();
        for (int cid = 0; cid < (int)comp_edges.size(); ++cid) {
            solve_component(cid);
        }
        vector<int> answer;
        for (int eid = 0; eid < m; ++eid) if (status[eid] == 1) answer.push_back(eid);
        sort(answer.begin(), answer.end());
        return answer;
    }
};

}  // namespace

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    Solver solver;
    solver.n = n;
    solver.m = (int)u.size();
    solver.U = move(u);
    solver.V = move(v);
    solver.adj.assign(n, {});
    for (int i = 0; i < solver.m; ++i) {
        solver.adj[solver.U[i]].push_back(i);
        solver.adj[solver.V[i]].push_back(i);
    }
    return solver.run();
}

int main() { 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 2017 -- Simurgh}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
We are given a connected graph.
The hidden set of royal roads is a spanning tree.
For one query we submit \emph{any} spanning tree and receive how many of its edges are royal.

\section{Bridges}
Every bridge must belong to every spanning tree, hence every bridge is immediately known to be
royal.
So we only need to solve the remaining 2-edge-connected components.

\section{Cycle Classification}
Suppose $C$ is a simple cycle.
Contract all vertices of $C$ into one supervertex and build any spanning forest of the remaining
graph.
Lifting that forest back gives a fixed edge set $F$ such that, for every edge $e \in C$,
\[
F \cup (C \setminus \{e\})
\]
is a spanning tree.

If we query this tree for every edge $e \in C$, the outside contribution $|F \cap R|$ is constant.
At least one edge of $C$ is non-royal (otherwise the hidden roads would contain a cycle), so the
maximum query value corresponds to omitting a non-royal edge.
Therefore:
\begin{itemize}
  \item omitted edge gives \textbf{maximum} value $\Longrightarrow$ non-royal;
  \item omitted edge gives value smaller by $1$ $\Longrightarrow$ royal.
\end{itemize}

\section{Ear Expansion}
Inside one 2-edge-connected component we maintain a connected subgraph whose edges are already
classified.
We start from one cycle, classify it as above, and then repeatedly add an ear:
\begin{itemize}
  \item an \emph{open ear}: a path whose endpoints are already in the classified subgraph and
        whose internal vertices are new;
  \item a \emph{closed ear}: a new cycle attached to exactly one already-known vertex.
\end{itemize}

For an ear $P$, let $Q$ be the already-known path between the two endpoints
(or $Q=\emptyset$ for a closed ear).
The cycle is $C=P \cup Q$.

\begin{itemize}
  \item If $Q$ already contains a known non-royal edge, one extra baseline query (omit that edge)
        is enough; then every edge of $P$ is classified by comparing its query value to the baseline.
  \item If every edge of $Q$ is known royal, then some edge of $P$ must be non-royal, so the
        maximum value among the queries that omit edges of $P$ is again the baseline.
\end{itemize}

Thus each new edge is classified with only $O(1)$ extra overhead.

\section{Finding the Next Ear}
We run a multi-source BFS from all vertices already in the classified subgraph, using only
unclassified edges of the current 2-edge-connected component.
The first collision yields either:
\begin{itemize}
  \item a path between two different known vertices, or
  \item a closed ear returning to the same known vertex.
\end{itemize}

\section{Complexity}
Let $m$ be the number of edges.
\begin{itemize}
  \item \textbf{Queries:} $O(m+n)$.
  \item \textbf{Graph work:} polynomial and easily fast enough for the official limits.
\end{itemize}

\section{Implementation}
\begin{lstlisting}
// 1. Find all bridges and mark them royal.
// 2. Decompose the remaining graph into 2-edge-connected components.
// 3. In each component:
//    - classify one initial cycle;
//    - repeatedly find an ear and classify all of its edges.
// 4. Return all edges marked royal.
\end{lstlisting}

\end{document}