Submission #99626

#	Time	Username	Problem	Language	Result	Execution time	Memory
99626		pustaczek	Torrent (COI16_torrent)	C++17	31 / 100	2051 ms	36728 KiB

torrent

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

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

struct Dummyf { template <typename... Ts> void operator()(Ts&&...) {} };
template <typename T, typename F> T binsearch(T a, T b, F f) {
    if (b - a == 0) return a;
    if (b - a == 1) return f(a) ? a : b;
    auto m = (a+b)/2;
    return f(m) ? binsearch(a, m, f) : binsearch(m+1, b, f);
}

struct Graph {
    Graph(int n):edges(n){}
    void addEdge1(int a, int b) { edges[a].push_back(b); }
    void addEdge2(int a, int b) { addEdge1(a, b); addEdge1(b, a); }
    int size() const { return (int)edges.size(); }
    template <typename Pre=Dummyf, typename Post=Dummyf, typename PreE=Dummyf, typename PostE=Dummyf, typename FailE=Dummyf> void DFS(int source, Pre pre, Post post, PreE pree, PostE poste, FailE faile) const {
        auto visit = vector<bool>(size(), false);
        implDFS(source, visit, pre, post, pree, poste, faile);
    }
    template <typename Pre=Dummyf, typename Post=Dummyf, typename PreE=Dummyf, typename PostE=Dummyf, typename FailE=Dummyf> void implDFS(int v, vector<bool>& visit, Pre pre, Post post, PreE pree, PostE poste, FailE faile) const {
        visit[v] = true;
        pre(v);
        for (auto u : edges[v])
            if (not visit[u])
                pree(v, u), implDFS(u, visit, pre, post, pree, poste, faile), poste(v, u);
            else
                faile(v, u);
        post(v);
    }
    vector<vector<int>> edges;
};

Graph loadEdges(int n, int m) {
    auto g = Graph(n);
    while (m --> 0)
        g.addEdge2(load<int>()-1, load<int>()-1);
    return g;
}

struct Roots {
    vector<bool> is;
    vector<int> vertices;
};

Roots researchRoots(int s1, int s2, int n, const Graph& tree) {
    auto root = vector<bool>(n, false);
    auto path = vector<int>({s2});
    root[s2] = true;
    tree.DFS(s1, {}, {}, {}, [&](int v, int u){
        if (root[u]) {
            root[v] = true;
            path.push_back(v);
        }
    }, {});
    reverse(path.begin(), path.end());
    return Roots{move(root), move(path)};
}

struct Cell {
    int requirement;
    vector<int> kids;
};

void partDynamic(int src, vector<bool>& visit, vector<Cell>& dyn, const Graph& tree) {
    tree.implDFS(src, visit, {}, [&](int v){
        sort(dyn[v].kids.begin(), dyn[v].kids.end(), [&](int u1, int u2) {
            return dyn[u1].requirement < dyn[u2].requirement;
        });
        dyn[v].requirement = 0;
        for (auto t=0; t<(int)dyn[v].kids.size(); ++t) {
            auto u = dyn[v].kids[(int)(dyn[v].kids.size())-t-1];
            dyn[v].requirement = max(dyn[v].requirement, t + 1 + dyn[u].requirement);
        }
    }, [&](int v, int u){
        dyn[v].kids.push_back(u);
    }, {}, {});
}

vector<Cell> brutCutDyn(int s1, int s2, int smr, int n, const Graph& tree, const Roots& root) {
    auto dyn = vector<Cell>(n, Cell{-1});
    auto visit = vector<bool>(n, false);
    visit[smr] = true;
    partDynamic(s1, visit, dyn, tree);
    visit[smr] = false;
    partDynamic(s2, visit, dyn, tree);
    return dyn;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto n = load<int>();
    auto s1 = load<int>() - 1;
    auto s2 = load<int>() - 1;
    auto tree = loadEdges(n, n-1);
    auto root = researchRoots(s1, s2, n, tree);
    auto answer = numeric_limits<int>::max();
    for (auto i=0; i+1<(int)root.vertices.size(); ++i) {
        auto dyn = brutCutDyn(s1, s2, root.vertices[i+1], n, tree, root);
        answer = min(answer, max(dyn[s1].requirement, dyn[s2].requirement));
    }
    cout << answer << '\n';
}

• Subtask 1: 31 / 31
• Subtask 2: 0 / 69