Submission #978580

#	Time	Username	Problem	Language	Result	Execution time	Memory
978580		michified	Torrent (COI16_torrent)	C++17	31 / 100	2040 ms	46344 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 best = INT_MAX;
    for (int i = 0; i < path.size() - 1; i++) {
        Solution sol(path[i], path[i + 1]);
        best = min(best, sol.ans());
    }

    cout << best;

    // 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;
    // }

    // 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;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < path.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~

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