oj.uz

Submission #639531

# Submission time Handle Problem Language Result Execution time Memory
639531 2022-09-10T13:37:43 Z FEDIKUS Torrent (COI16_torrent) C++17
100 / 100
 379 ms 27144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=3e5+10;
vector<int> g[maxn];
stack<int> tren;
vector<int> put;
int duzine[maxn];
int a,b;

bool dfs1(int cvor,int prosli){
    tren.push(cvor);
    if(cvor==b) return true;
    for(int i:g[cvor]){
        if(i==prosli) continue;
        if(dfs1(i,cvor)) return true;
    }
    tren.pop();
    return false;
}

int dfs2(int cvor,int prosli,int k1,int k2){
    int cena=0;
    vector<int> val;
    for(int i:g[cvor]){
        if((cvor==k1 && i==k2) || (cvor==k2 && i==k1)) continue;
        if(i==prosli) continue;
        val.pb(dfs2(i,cvor,k1,k2));
    }
    sort(val.begin(),val.end());
    int k=val.size();
    for(int i:val){
        cena=max(cena,i+(k--));
    }
    return cena;
}

int dfs3(int cvor,int prosli,int k1,int k2){
    int ret=1;
    for(int i:g[cvor]){
        if(i==prosli || i==k1 || i==k2) continue;
        ret+=dfs3(i,cvor,k1,k2);
    }
    return ret;
}

void solve(){
    int n;
    cin>>n;
    cin>>a>>b;
    for(int i=1;i<n;i++){
        int c,d;
        cin>>c>>d;
        g[c].pb(d);
        g[d].pb(c);
    }
    dfs1(a,-1);
    while(!tren.empty()){
        put.pb(tren.top());
        tren.pop();
    }
    int res=INT_MAX;
    int l=0;
    int r=put.size()-2;
    while(l<=r){
        int mid=l+(r-l)/2;
        int sta2=dfs2(a,-1,put[mid],put[mid+1]);
        int sta1=dfs2(b,-1,put[mid],put[mid+1]);
        res=min(res,max(sta1,sta2));
        if(sta1==sta2){
            break;
        }
        if(sta1>sta2){
            r=mid-1;
        }else if(sta1<sta2) l=mid+1;
    }
    cout<<res;
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7332 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 23492 KB Output is correct
2 Correct 372 ms 25068 KB Output is correct
3 Correct 379 ms 26656 KB Output is correct
4 Correct 378 ms 26056 KB Output is correct
5 Correct 336 ms 23248 KB Output is correct
6 Correct 323 ms 23576 KB Output is correct
7 Correct 342 ms 27144 KB Output is correct