Submission #956758

#	Time	Username	Problem	Language	Result	Execution time	Memory
956758		uped	Torrent (COI16_torrent)	C++14	0 / 100	176 ms	24600 KiB

torrent

#include <bits/stdc++.h>

#define DEBUG(x) cout << #x << ": " << x << '\n';

using namespace std;
using ll = long long;

const int N = 3e5;

int n, a, b;
vector<int> adj[N];
//int sz[N];
stack<int> on_path;
bool is_on_path[N];
vector<int> path;

bool find_path(int n, int p = -1) {
    on_path.push(n);
    if (n == b) return true;

    for (int x : adj[n]) {
        if (x == p) continue;
        if (find_path(x, n)) return true;
    }
    on_path.pop();
    return false;
}

int dp[N];

void dfs(int n, int p = -1) {
    vector<int> cur;
    for (int x : adj[n]) {
        if (x == p || is_on_path[x]) continue;
        dfs(x, n);
        cur.push_back(dp[x]);
    }
    sort(cur.begin(), cur.end(), greater<>());
    for (int i = 0; i < cur.size(); ++i) {
        dp[n] = max(dp[n], cur[i] + i + 1);
    }
}

bool check(int x) {
    int mx_left = -1;
    int cur_t = 0;
    for (int i = 0; i < path.size() - 1; ++i) {
        int diff = x - dp[path[i]] - cur_t;
        if (diff < 0) break; // can't solve
        if (diff == 0) {
            mx_left = i;
            break;
        }
        cur_t += diff;
        mx_left = i;
    } 
    cur_t = 0;
    int mx_right = path.size();
    for (int i = path.size() - 1; i > 0; --i) {
        int diff = x - dp[path[i]] - cur_t;
        if (diff < 0) break; // can't solve
        if (diff == 0) {
            mx_right = i;
            break;
        }
        cur_t += diff;
        mx_right = i;
    }
    return mx_right - mx_left <= 1;
}

int main() {
    cin >> n >> a >> b;
    --a; --b;
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    find_path(a);
    while(!on_path.empty()) {
        path.push_back(on_path.top());
        on_path.pop();
        is_on_path[path.back()] = true;
    }
    reverse(path.begin(), path.end());
    for (int x : path) {
        dfs(x);
    }
    int l = 0, r = 2 * N;
    while (r > l + 1) {
        int m = (l + r) / 2;
        if (check(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << r;
}

Compilation message (stderr)

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

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