oj.uz

Submission #1067952

# Submission time Handle Problem Language Result Execution time Memory
1067952 2024-08-21T06:00:40 Z Plurm Torrent (COI16_torrent) C++11
100 / 100
 78 ms 24792 KB 
#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

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.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 20800 KB Output is correct
2 Correct 64 ms 22352 KB Output is correct
3 Correct 69 ms 22224 KB Output is correct
4 Correct 66 ms 23520 KB Output is correct
5 Correct 78 ms 21680 KB Output is correct
6 Correct 61 ms 20780 KB Output is correct
7 Correct 62 ms 24792 KB Output is correct