oj.uz

Submission #1024448

# Submission time Handle Problem Language Result Execution time Memory
1024448 2024-07-16T05:21:50 Z KasymK Torrent (COI16_torrent) C++17
100 / 100
 234 ms 28872 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define pii pair<int, int>
#define wr puts("---------------")
#define all(v) v.begin(), v.end()
const int N = 3e5+5;
vector<int> adj[N];
int par[N], big[N];

void dfs(int x, int pr){
    par[x] = pr;
    for(auto i : adj[x])
        if(i != pr)
            dfs(i, x);
}

void dfs_(int x, int pr, int _){
    vector<int> kk;
    for(auto i : adj[x])
        if(i != pr and i != _)
            dfs_(i, x, _), kk.pb(big[i]);
    sort(all(kk));
    int sz = (int)kk.size();
    for(int i = 0; i < sz; ++i)
        big[x] = max(big[x], kk[i]+sz-i);
}

int main(){
    int n, a, b;
    vector<int> v;
    scanf("%d%d%d", &n, &a, &b);
    for(int i = 0; i < n-1; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(a, a);
    v.pb(b);
    while(v.back() != a)
        v.pb(par[v.back()]);
    int l = 0, r = v.size()-2, ans = INT_MAX;
    while(l <= r){
        memset(big, 0, sizeof big);
        int mid = (l+r)/2;
        dfs_(a, a, v[mid]);
        dfs_(b, b, v[mid+1]);
        ans = min(ans, max(big[a], big[b]));
        if(big[a] < big[b])
            r = mid-1;
        else
            l = mid+1;
    }
    printf("%d", ans);
    return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d%d", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 25508 KB Output is correct
2 Correct 195 ms 26848 KB Output is correct
3 Correct 218 ms 28488 KB Output is correct
4 Correct 234 ms 27952 KB Output is correct
5 Correct 197 ms 25172 KB Output is correct
6 Correct 209 ms 25796 KB Output is correct
7 Correct 210 ms 28872 KB Output is correct