Submission #1026159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026159		amine_aroua	Torrent (COI16_torrent)	C++17	100 / 100	315 ms	22664 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
int a , b;
vector<int> adj[MAXN];
int par[MAXN];
bool vis[MAXN];
int n;
void dfs1(int x , int p = 0)
{
    par[x] = p;
    for(auto u : adj[x])
    {
        if(u == p)
            continue;
        dfs1(u , x);
    }
}
int dfs(int x , int p)
{
    if(vis[x])
        return 0;
    vector<int> v;
    for(auto u : adj[x])
    {
        if(u == p || vis[u])
            continue;
        v.push_back(dfs(u , x));
    }
    sort(v.begin() , v.end());
    int mx = 0;
    for(int i = 0 ; i < (int)v.size() ; i++)
    {
        mx = max(mx , v[i] + (int)v.size() - i);
    }
    return mx;
}
bool check(int mid)
{
    for(int i = 1 ; i <= n ; i++)
        vis[i] = 0;
    int t = 0;
    int cur = b;
    while(cur)
    {
        int cur_t = dfs(cur , par[cur]);
        if(cur_t + t > mid)
            break;
        vis[cur] = 1;
        t++;
        cur = par[cur];
    }
    return dfs(a , 0) <= mid;
}
int main() {
    cin>>n;
    cin>>a>>b;
    vector<pair<int ,int>> edg;
    for(int i = 0 ; i < n - 1 ; i++)
    {
        int x , y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs1(a);
    int l = 0 , r = 2*n;
    while(l + 1 < r)
    {
        int mid = (l + r)/2;
        if(check(mid - 1))
            r = mid;
        else
            l = mid;
    }
    cout<< r - 1;
}

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