Submission #1092266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092266		coldbr3w	Torrent (COI16_torrent)	C++17	100 / 100	278 ms	31004 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,a,b;
vector<ll>adj[N];
ll dp[N];
vector<ll>order, path;
void dfs_path(ll u, ll par){
    order.pb(u);
    if(u == b) path = order;
    for(auto v : adj[u]){
        if(v == par) continue;
        dfs_path(v, u);
    }
    order.pop_back();
}
void dfs(ll u, ll par, ll tar){
    dp[u] = 1;
    vector<ll>vec;
    for(auto v : adj[u]){
        if(v == par || v == tar) continue;
        dfs(v, u, tar);
        vec.pb(dp[v]);
    }
    sort(all(vec), greater<ll>());
    ll mx = 0;
    for(int i = 0; i < vec.size();i++) mx = max(mx, vec[i] + i);
    dp[u] += mx;
}
ll calc(ll x, ll tar){
    for(int i = 1; i <= n;i++) dp[i] = 0;
    dfs(x, 0, tar);
    return dp[x] - 1;
}
void to_thic_cau(){
    cin >> n >> a >> b;
    for(int i = 1; i <= n - 1;i++){
        ll u,v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    dfs_path(a, 0);
    ll l = 0, r = (ll)path.size() - 2, pos = -1;
    while(l <= r){
        ll mid = (l + r) / 2;
        if(calc(a, path[mid + 1]) <= calc(b, path[mid])){
            pos = mid; l = mid + 1;
        }
        else r = mid - 1;
    }
    ll res = inf;
    if(pos != -1) res = max(calc(a, path[pos + 1]), calc(b, path[pos]));
    pos++;
    if(pos + 1 < path.size()) res = min(res, max(calc(a, path[pos + 1]), calc(b, path[pos])));
    cout << res << "\n";
}

signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Compilation message (stderr)

torrent.cpp: In function 'void dfs(long long int, long long int, long long int)':
torrent.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < vec.size();i++) mx = max(mx, vec[i] + i);
      |                    ~~^~~~~~~~~~~~
torrent.cpp: In function 'void to_thic_cau()':
torrent.cpp:64:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(pos + 1 < path.size()) res = min(res, max(calc(a, path[pos + 1]), calc(b, path[pos])));
      |        ~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69