oj.uz

Submission #978619

# Submission time Handle Problem Language Result Execution time Memory
978619 2024-05-09T11:36:10 Z michified Torrent (COI16_torrent) C++17
100 / 100
 594 ms 69436 KB 
#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 lans() {
        return nodes[a].reqt;
    }

    int rans() {
        return 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);
    vector<pair<int, int>> es;
    for (i = 0; i < path.size() - 1; i++) es.pb({path[i], path[i + 1]});

    int l = 0, r = es.size() - 1, mid;
    while (l < r - 1) {
        mid = (l + r) / 2;
        Solution res(es[mid].first, es[mid].second);
        if (res.lans() > res.rans()) l = mid;
        else r = mid;
    }

    if (path.size() == 1) {
        Solution sol(a, b);
        cout << max(sol.rans(), sol.lans());
        return 0;
    }

    Solution left(es[l].first, es[l].second), right(es[l + 1].first, es[l + 1].second);
    if (max(left.lans(), left.rans()) > max(right.lans(), right.rans())) cout << max(right.lans(), right.rans());
    else cout << max(left.lans(), left.rans());
    return 0;
}

Compilation message

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

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 59388 KB Output is correct
2 Correct 584 ms 65324 KB Output is correct
3 Correct 561 ms 66692 KB Output is correct
4 Correct 591 ms 68812 KB Output is correct
5 Correct 583 ms 64880 KB Output is correct
6 Correct 545 ms 65364 KB Output is correct
7 Correct 563 ms 69436 KB Output is correct