oj.uz

Submission #474550

# Submission time Handle Problem Language Result Execution time Memory
474550 2021-09-19T02:46:43 Z Saacoota Torrent (COI16_torrent) C++14
100 / 100
 646 ms 41084 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ii pair < int , int >

using namespace std;

const int maxn = 3e5 + 5;

int p[maxn] , id[maxn] , dp[maxn] , chl[maxn];
int u[maxn] , v[maxn];
bool vs[maxn];
vector < ii > g[maxn];
vector < int > adj[maxn] , vc;
int n , a , b;

void DFS(int u) {
    for (auto v : g[u])
    if (p[u] != v.fi) {
        p[v.fi] = u;
        id[v.fi] = v.se;
        DFS(v.fi);
    }
}

void init(int u,int ban) {
    vs[u] = true;
    chl[u] = 1;
    for (auto v : g[u])
    if (!vs[v.fi] && v.se != ban) {
        adj[u].push_back(v.fi);
        chl[u] += chl[v.fi];
        init(v.fi , ban);
    }
}

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

void GO(int u) {
    for (int i = 0 ; i < adj[u].size() ; ++i) {
        int v = adj[u][i];
        GO(v);
    }
    sort(adj[u].begin(),adj[u].end(),cmp);
    for (int i = 0 ; i < adj[u].size() ; ++i)
    dp[u] = max(dp[u] , dp[adj[u][i]] + i + 1);
}

int get(int root,int ban) {
    for (int i = 1 ; i <= n ; ++i) {
        vs[i] = chl[i] = dp[i] = 0;
        adj[i].clear();
    }
    init(root , ban);
    GO(root);
    return dp[root];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> a >> b;
    for (int i = 1 ; i < n ; ++i) {
        cin >> u[i] >> v[i];
        g[u[i]].emplace_back(v[i] , i);
        g[v[i]].emplace_back(u[i] , i);
    }
    DFS(a);
    int tmp = b;
    while (tmp != a) {
        vc.push_back(id[tmp]);
        tmp = p[tmp];
    }
    int l = 0;
    int r = vc.size() - 1;
    int res = 1e9;
    while (l <= r) {
        int mid = l + r >> 1;
        int vala = get(a , vc[mid]);
        int valb = get(b , vc[mid]);
        res = min(res , max(vala , valb));
        if (vala > valb) l = mid + 1;
        else r = mid - 1;
    }
    cout << res;
}

Compilation message

torrent.cpp: In function 'void GO(int)':
torrent.cpp:42:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0 ; i < adj[u].size() ; ++i) {
      |                      ~~^~~~~~~~~~~~~~~
torrent.cpp:47:24: 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 < adj[u].size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~~
torrent.cpp: In function 'int get(int, int)':
torrent.cpp:53:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   53 |         vs[i] = chl[i] = dp[i] = 0;
      |                 ~~~~~~~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14532 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 9 ms 14544 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 38284 KB Output is correct
2 Correct 646 ms 39384 KB Output is correct
3 Correct 595 ms 40128 KB Output is correct
4 Correct 552 ms 40372 KB Output is correct
5 Correct 545 ms 38392 KB Output is correct
6 Correct 513 ms 38732 KB Output is correct
7 Correct 482 ms 41084 KB Output is correct