Submission #1118459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118459		alexdd	Race (IOI11_race)	C++17	21 / 100	1020 ms	262144 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long rez,K;
vector<pair<long long,long long>> con[200005];
map<long long,long long> dp[200005];
long long d[200005],d2[200005];
void dfs(int nod, int par)
{
    if(d2[nod]==K) rez = min(rez, d[nod]);
    long long maxc=-1,heavy=-1;
    for(auto [adj,w]:con[nod])
    {
        if(adj==par)
            continue;
        d[adj] = d[nod] + 1;
        d2[adj] = d2[nod] + w;
        dfs(adj,nod);
        if((int)dp[adj].size() > maxc)
            maxc = dp[adj].size(), heavy=adj;
    }
    if(heavy==-1)
    {

    }
    else
    {
        swap(dp[nod], dp[heavy]);
        for(auto [adj,w]:con[nod])
        {
            if(adj==par || adj==heavy)
                continue;
            for(auto it:dp[adj])
            {
                rez = min(rez, it.second + dp[nod][K+2*d2[nod]-it.first] + 2LL*INF - 2LL*d[nod]);
                ///it.first + x - 2*d2[nod] = K
            }
            for(auto it:dp[adj])
                dp[nod][it.first] = min(dp[nod][it.first], it.second);
        }
    }
    rez = min(rez, dp[nod][K+d2[nod]] + INF - d[nod]);
    ///x - d2[nod] = K
    dp[nod][d2[nod]] = min(dp[nod][d2[nod]], d[nod] - INF);
}
int best_path(int N, int copK, int H[][2], int L[])
{
    K = copK;
    rez = N+2;
    for(int i=0;i<N-1;i++)
    {
        con[H[i][0]].push_back({H[i][1],L[i]});
        con[H[i][1]].push_back({H[i][0],L[i]});
    }
    dfs(0,-1);
    if(rez==N+2)
        rez=-1;
    return rez;
}

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