oj.uz

Submission #474546

# Submission time Handle Problem Language Result Execution time Memory
474546 2021-09-19T02:37:13 Z ThaiBaHung Torrent (COI16_torrent) C++14
100 / 100
 550 ms 29404 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 4;
int n, x, y;
int socon[3][N];
vector < int > adj[N];
int cha[3][N];
int L[N], R[N];
vector < int > path;
bool kt[N];
int dp[N];

void dfs(int i, int j, int id)
{
    socon[id][i] = 1;
    for (int u : adj[i])
    {
        if (u == j) continue;
        dfs(u, i, id);
        cha[id][u] = i;
        socon[id][i] += socon[id][u];
    }
}

bool cmp(int a, int b)
{
    return dp[a] > dp[b];
}

void xuly(int i, int j, int dif)
{
    dp[i] = 0;
    vector < int > con;

    for (int u : adj[i])
    {
        if (u == j) continue;
        if (u == dif) continue;
        xuly(u, i, dif);
        con.push_back(u);
    }

    if (con.size() == 0)
    {
        dp[i] = 1;
        return;
    }

    sort(con.begin(), con.end(), cmp);

    for (int t = 0; t < con.size(); t++)
    {
        dp[i] = max(dp[i], dp[con[t]] + t + 1);
       // if (i == x) cout << con[t] << " " << dp[con[t]] << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("t.inp","r",stdin); freopen("t.out","w",stdout);

    cin >> n >> x >> y;

    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
        kt[u] = kt[v] = false;
    }

    dfs(x, 0, 1);
    dfs(y, 0, 2);

    int node = x;
    while (node != 0) {path.push_back(node); node = cha[2][node];}
    int lo = 0, hi = path.size() - 2;

    int res = 1e9 + 7;

    if (n <= 1000)
    {
        for (int i = 0; i < path.size() - 1; i++)
        {
            xuly(x, 0, path[i + 1]);
            xuly(y, 0, path[i]);
            res = min(res, max(dp[x], dp[y]) - 1);
        }

        cout << res;
        return 0;
    }

//    for (int u : path)
//        cout << u << " ";

    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;

        //cout << path[mid] << " ";

        xuly(x, 0, path[mid + 1]);
        xuly(y, 0, path[mid]);
        res = min(res, max(dp[x], dp[y]) - 1);
        //cout << dp[x] << " " << dp[y] << '\n';

        if (dp[x] > dp[y]) hi = mid - 1;
        else lo = mid + 1;
    }

    cout << res;
}

Compilation message

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

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7372 KB Output is correct
2 Correct 9 ms 7372 KB Output is correct
3 Correct 16 ms 7372 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 26056 KB Output is correct
2 Correct 536 ms 27844 KB Output is correct
3 Correct 517 ms 28760 KB Output is correct
4 Correct 550 ms 29136 KB Output is correct
5 Correct 502 ms 25500 KB Output is correct
6 Correct 451 ms 25728 KB Output is correct
7 Correct 443 ms 29404 KB Output is correct