Submission #978599

#	Time	Username	Problem	Language	Result	Execution time	Memory
978599		michified	Torrent (COI16_torrent)	C++17	0 / 100	1067 ms	63348 KiB

torrent

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

struct node_t {
    int par;
    vector<int> childs;
};

int n, a, b;
vector<vector<int>> adj;
vector<int> path;
vector<node_t> nodes;

class Solution {
public:
    struct node_t {
        int par, reqt;
        vector<int> childs;
    };

    int ru, rv;
    vector<node_t> nodes;

    void rootTree(int cur, int par) {
        node_t& u = nodes[cur];
        if (par != -1) u.par = par;
        for (int v : adj[cur]) {
            if (v == par or (cur == ru and v == rv) or (cur == rv and v == ru)) continue;
            u.childs.pb(v);
            rootTree(v, cur);
        }
    }

    void dfs(int cur) {
        node_t& u = nodes[cur];
        priority_queue<int> pq;
        for (int v : u.childs) {
            dfs(v);
            pq.push(nodes[v].reqt);
        }
        int t = 1;
        while (not pq.empty()) {
            u.reqt = max(u.reqt, pq.top() + t);
            pq.pop();
            t++;
        }
    }

    int ans() {
        return max(nodes[a].reqt, nodes[b].reqt);
    }

    Solution(int ru, int rv) { // restricted vertices
        this -> ru = ru;
        this -> rv = rv;
        nodes.resize(n + 1);
        rootTree(a, -1);
        rootTree(b, -1);
        dfs(a);
        dfs(b);
    }
};

void rootTree(int cur, int par) {
    node_t& u = nodes[cur];
    if (par != -1) u.par = par;
    for (int v : adj[cur]) {
        if (v == par) continue;
        u.childs.pb(v);
        rootTree(v, cur);
    }
}

void findPath(int cur) {
    path.pb(cur);
    if (cur == a) return;
    findPath(nodes[cur].par);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> a >> b;
    adj.resize(n + 1);
    nodes.resize(n + 1);

    int tu, tv, i;
    for (i = 0; i < n - 1; i++) {
        cin >> tu >> tv;
        adj[tu].pb(tv);
        adj[tv].pb(tu);
    }

    rootTree(a, -1);
    findPath(b);

    int l = 0, r = path.size() - 2, mid;
    while (l < r - 1) {
        mid = (l + r) / 2;
        Solution left(path[mid], path[mid + 1]), right(path[mid + 1], path[mid + 2]);
        if (left.ans() >= right.ans()) l = mid;
        else r = mid;
    }

    if (path.size() == 2) {
        Solution sol(path[0], path[1]);
        cout << sol.ans();
        return 0;
    }

    Solution left(path[l], path[l + 1]), right(path[l + 1], path[l + 2]);
    if (left.ans() > right.ans()) cout << right.ans();
    else cout << left.ans();
    return 0;
}

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