Submission #1147424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147424		aminjon__	Race (IOI11_race)	C++20	0 / 100	1 ms	320 KiB

race

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define endl '\n'
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;

#include "race.h"
int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pair<ll,ll>>>rebr(N+1);
    for(int i = 0;i < N-1;i++){
        rebr[H[i][0]].push_back({H[i][1],L[i]});
        rebr[H[i][1]].push_back({H[i][0],L[i]});
    }
    ll ans = LLONG_MAX;
    
    function< set< pair<ll,ll> >(ll ,ll,ll , ll)> dfs;
    
    dfs = [&](ll x , ll p , ll sum , ll depth){
        
        set< pair<ll,ll> > Suffix;  
        Suffix.insert({sum , depth});
        for(auto g: rebr[x]){
            if(g.first==p)continue;
            
             set< pair<ll,ll> > govno = dfs(g.first , x , sum+g.second ,depth+1);
            
            if(Suffix.size() < govno.size()){
                swap(govno, Suffix);
            }
            for(auto g: govno){
                Suffix.insert(g);
            }
        }
        
        for(auto g: Suffix){
            if(g.first == sum+K){
                ans = min(g.second-depth ,ans);
                continue;
            }
            auto r = Suffix.upper_bound({sum+sum+K - g.first , 0});
            if(r != Suffix.end() && (r->first) == sum+sum+K - g.first){
                ans = min(ans , g.second+(r->second) - (depth*2) );
            }
            
        }
        
        return Suffix;
    };
    
    dfs(1 , 0 , 0 , 0);
    
    
    
    
    
  return (ans == LLONG_MAX ? -1 : ans);
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57