Submission #1024448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024448		KasymK	Torrent (COI16_torrent)	C++17	100 / 100	234 ms	28872 KiB

torrent

#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 (stderr)

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 / 31
• Subtask 2: 69 / 69