Submission #726939

#	Time	Username	Problem	Language	Result	Execution time	Memory
726939		grogu	Torrent (COI16_torrent)	C++14	100 / 100	495 ms	30848 KiB

torrent

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;

#define maxn 300005
ll n,x,y;
vector<ll> g[maxn];
vector<ll> cur;
bool naso = 0;
void dfs1(ll u,ll p,ll en){
    cur.pb(u);
    if(u==en){naso = 1;return;}
    for(ll s : g[u]){
        if(s==p) continue;
        dfs1(s,u,en);
        if(naso) return;
    }
    cur.popb();
}
pll ans[maxn];
pll bad;
bool chk(ll x,ll y){
    if(x==bad.fi&&y==bad.sc) return 1;
    swap(x,y);
    if(x==bad.fi&&y==bad.sc) return 1;
    return 0;
}
ll dfs(ll u,ll p){
    vector<ll> v;
    for(ll s : g[u]){
        if(s==p) continue;
        if(chk(u,s)) continue;
        v.pb(dfs(s,u));
    }
    sort(all(v));
    reverse(all(v));
    ll ans = 0;
    for(ll i = 0;i<v.size();i++) ans = max(ans,v[i]+i+1);
    return ans;
}
pll f(ll i){
    if(i<=-1) return {llinf,llinf};
    if(i>=cur.size()-1) return {llinf,llinf};
    if(ans[i].fi!=-1) return ans[i];
    bad = {cur[i],cur[i+1]};
    return ans[i] = {dfs(x,x),dfs(y,y)};
}
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> x >> y;
    for(ll i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs1(x,x,y);
    ll l = 0,r = cur.size()-2,mid,rez = cur.size()-2;
    for(ll i = 0;i<=cur.size()-2;i++) ans[i] = {-1,-1};
    ans[cur.size()-1] = {llinf,llinf};
    bool e = f(0).fi > f(0).fi;
    while(l<=r){
        ll mid = (l+r)/2;
        if((f(mid).fi>f(mid).sc)==e) rez = mid,l = mid+1;
        else r = mid-1;
    }
    ll ans = llinf;
    for(ll i = rez-2;i<=rez+2;i++){
        ans = min(ans,max(f(i).fi,f(i).sc));
    }
    cout<<ans<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}
/**
6 2 1
1 2
2 3
2 4
1 5
5 6

10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10

17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2
**/

Compilation message (stderr)

torrent.cpp: In function 'long long int dfs(long long int, long long int)':
torrent.cpp:53:19: 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]
   53 |     for(ll i = 0;i<v.size();i++) ans = max(ans,v[i]+i+1);
      |                  ~^~~~~~~~~
torrent.cpp: In function 'std::pair<long long int, long long int> f(long long int)':
torrent.cpp:58:9: 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]
   58 |     if(i>=cur.size()-1) return {llinf,llinf};
      |        ~^~~~~~~~~~~~~~
torrent.cpp: In function 'void tc()':
torrent.cpp:73:19: 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]
   73 |     for(ll i = 0;i<=cur.size()-2;i++) ans[i] = {-1,-1};
      |                  ~^~~~~~~~~~~~~~
torrent.cpp:72:31: warning: unused variable 'mid' [-Wunused-variable]
   72 |     ll l = 0,r = cur.size()-2,mid,rez = cur.size()-2;
      |                               ^~~

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