Submission #1067952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067952		Plurm	Torrent (COI16_torrent)	C++11	100 / 100	78 ms	24792 KiB

torrent

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

vector<int> g[300005];
int dep[300005];
int chcnt[300005];
int col[300005];
int dp[300005];
bool mainline[300005];
int dfs(int u, int p = -1) {
    vector<int> vec;
    for (int v : g[u]) {
        if (v == p)
            continue;
        if (mainline[v])
            continue;
        dfs(v, u);
        vec.push_back(dp[v]);
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++) {
        dp[u] = max(dp[u], vec[i] + i + 1);
    }
    return dp[u];
}
vector<int> line;
bool linesearch(int u, int t, int p = -1) {
    if (u == t) {
        mainline[u] = true;
        line.push_back(u);
        return true;
    }
    for (int v : g[u]) {
        if (v == p)
            continue;
        if (linesearch(v, t, u)) {
            mainline[u] = true;
            line.push_back(u);
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    linesearch(b, a);
    for (int u : line) {
        dfs(u);
    }
    // cout << "DBGDP " << dp[1] << " " << dp[2] << " " << dp[3] << " " << dp[4]
    //  << endl;
    int lo = 0;
    int hi = n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        int modi = 0;
        int last = line.size();
        for (int i = 0; i < line.size(); i++) {
            if (dp[line[i]] + modi > mid) {
                last = i - 1;
                break;
            } else if (dp[line[i]] + modi + 1 > mid) {
                modi += 2;
            } else {
                modi++;
            }
        }
        int first = 0;
        modi = 0;
        for (int i = line.size() - 1; i >= 0; i--) {
            if (dp[line[i]] + modi > mid) {
                first = i + 1;
                break;
            } else if (dp[line[i]] + modi + 1 > mid) {
                modi += 2;
            } else {
                modi++;
            }
        }
        // cout << "DBG " << mid << " " << first << " " << last << endl;
        if (last + 1 >= first) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    cout << lo << endl;
    return 0;
}

Compilation message (stderr)

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

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