Submission #944632

#	Time	Username	Problem	Language	Result	Execution time	Memory
944632		beepbeepsheep	Race (IOI11_race)	C++17	100 / 100	385 ms	105708 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
const ll maxn=2e5+5;
const ll inf=1e15;
const ll mod=1e9+7;

ll ans=inf;
vector<ii> adj[maxn];
ll n,k;
map<ll,ll> maps[maxn];
pair<ll,ll> solve(ll n, ll p){
    maps[n].insert({0,0});
    ll off=0;
    ll off2=0;
    ll b,c;
    for (auto u:adj[n]){
        if (u.first==p) continue;
        tie(b,c)=solve(u.first,n);
        b+=u.second;
        c++;
        map<ll,ll> &a=maps[u.first];
        if (maps[n].size()<a.size()) swap(maps[n],a),swap(off,b),swap(off2,c);
        for (auto v:a){
            auto it=maps[n].find(k-v.first-b-off);
            if (it!=maps[n].end()){
                ans=min(ans,it->second+v.second+off2+c);
            }
        }
        for (auto v:a){
            if (maps[n].find(v.first+b-off)==maps[n].end()){
                maps[n][v.first+b-off]=v.second+c-off2;
            } else{
                maps[n][v.first+b-off]=min(maps[n][v.first+b-off],v.second+c-off2);
            }
        }
    }
    return {off,off2};
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N,k=K;
    for (int i=0;i<n-1;i++){
        adj[H[i][0]].emplace_back(H[i][1],L[i]);
        adj[H[i][1]].emplace_back(H[i][0],L[i]);
    }
    solve(0,-1);
    return (ans==inf?-1:ans);
}

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