oj.uz

Submission #476507

# Submission time Handle Problem Language Result Execution time Memory
476507 2021-09-27T12:24:01 Z DJ035 Torrent (COI16_torrent) C++17
100 / 100
 541 ms 35248 KB 
#include <bits/stdc++.h>
#define MEM 300005
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll MOD = 1e9+7;
const ll INF = 1e10+7;
ll t,n,m,a,b,ce;
ll v[MEM];
vector<pi> g[MEM];
vector<ll> d,f;
void dfs(ll s, ll e){
    v[s] = 1;
    if(s==b) {
        f = d;
        return;
    }
    for(pi nt: g[s]){
        if(v[nt.x] || e==nt.x) continue;
        d.pb(nt.y);
        dfs(nt.x,s);
        d.pop_back();
    }
}
ll DP(ll c, ll p){
    vector<ll> dp;
    for(pi sb: g[c]){
        if(p==sb.x || sb.y==ce) continue;
        dp.pb(-DP(sb.x,c));
    }
    sort(all(dp));
    ll ans=0;
    for(int i=0; i<dp.size(); i++)
        ans = max(ans, -dp[i]+i+1);
    return ans;
}
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for(int i=1; i<n; i++){
        ll q1,q2;
        cin >> q1 >> q2;
        g[q1].pb({q2,i});
        g[q2].pb({q1,i});
    }
    dfs(a,-1);
    ll l=0, r=f.size()-1,res=0;
    while(l<=r){
        ll mid = (l+r)>>1;
        ce = f[mid];
        if(DP(a,-1)<DP(b,-1)) l = mid+1, res = mid;
        else r = mid-1;
    }
    ce = f[res];
    ll ans=max(DP(a,-1),DP(b,-1));
    if(res<f.size()-1){
        res++;
        ce = f[res];
        ans = min(ans, max(DP(a,-1),DP(b,-1)));
    }
    cout << ans;
}

Compilation message

torrent.cpp: In function 'll DP(ll, ll)':
torrent.cpp:38:19: 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<dp.size(); i++)
      |                  ~^~~~~~~~~~
torrent.cpp: At global scope:
torrent.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      | ^~~~
torrent.cpp: In function 'int main()':
torrent.cpp:62:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if(res<f.size()-1){
      |        ~~~^~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 4 ms 7368 KB Output is correct
3 Correct 5 ms 7452 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 30700 KB Output is correct
2 Correct 490 ms 32132 KB Output is correct
3 Correct 492 ms 34352 KB Output is correct
4 Correct 487 ms 33580 KB Output is correct
5 Correct 520 ms 30504 KB Output is correct
6 Correct 541 ms 31340 KB Output is correct
7 Correct 433 ms 35248 KB Output is correct