Submission #964086

#	Time	Username	Problem	Language	Result	Execution time	Memory
964086		maxFedorchuk	Race (IOI11_race)	C++17	100 / 100	364 ms	115376 KiB

race

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

const long long MX=2e5+10;
const long long INF=1e18;

vector < pair < long long , long long > > mas[MX];
set < pair < long long , long long > > st[MX];
long long dep[MX],vid[MX],ans=INF,kk;

void DFS(long long zar,long long mun)
{
    st[zar].insert({vid[zar],dep[zar]});

    for(auto [nxt,ds]:mas[zar])
    {
        if(nxt==mun)
        {
            continue;
        }

        vid[nxt]=vid[zar]+ds;
        dep[nxt]=dep[zar]+1;
        DFS(nxt,zar);

        if(st[zar].size()<st[nxt].size())
        {
            swap(st[zar],st[nxt]);
        }

        for(auto [rz,gl]:st[nxt])
        {
            auto it=st[zar].lower_bound({(kk+2*vid[zar])-rz,0});

            if(it!=st[zar].end())
            {
                if((*it).first+rz==kk+2*vid[zar])
                {
                    ans=min(ans,gl+(*it).second-2*dep[zar]);
                }
            }
        }

        for(auto u:st[nxt])
        {
            st[zar].insert(u);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) 
{
    kk=K;

    for(long long i=0;i<N-1;i++)
    {
        mas[H[i][0]].push_back({H[i][1],L[i]});
        mas[H[i][1]].push_back({H[i][0],L[i]});
    }

    vid[0]=0;
    dep[0]=0;
    DFS(0,0);

    return ((ans==INF)?-1:ans);
}

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