oj.uz

Submission #1026159

# Submission time Handle Problem Language Result Execution time Memory
1026159 2024-07-17T16:10:36 Z amine_aroua Torrent (COI16_torrent) C++17
100 / 100
 315 ms 22664 KB 
#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.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 20560 KB Output is correct
2 Correct 277 ms 21584 KB Output is correct
3 Correct 276 ms 21788 KB Output is correct
4 Correct 315 ms 22664 KB Output is correct
5 Correct 302 ms 20064 KB Output is correct
6 Correct 302 ms 21188 KB Output is correct
7 Correct 279 ms 22648 KB Output is correct