Submission #1218654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218654		a.pendov	Race (IOI11_race)	C++20	0 / 100	5 ms	10560 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=1000000009;
const long long MAXN=100009;
const long long MAXK=1000009;
vector<pair<int,int>> edg[MAXN];
long long pod[MAXN];
long long father[MAXN];
long long best[MAXK];
bool hasBeenCentr[MAXN];
long long k,ans=inf;

vector<pair<int,int>> v;

inline long long min1(long long a,long long b)
{
    if(a>b)return b;
    return a;
}

long long dfs(int curr,int f)
{
    father[curr]=f;
    pod[curr]=1;
    for(auto i:edg[curr])
    {
        if(i.first==f||hasBeenCentr[i.first])continue;
        pod[curr]+=dfs(i.first,curr);
    }

    return pod[curr];
}

long long centr(int curr,int sz)
{
    for(auto i:edg[curr])
    {
        if(i.first==father[curr]||hasBeenCentr[i.first])continue;
        if(pod[i.first]>sz/2)return centr(i.first,sz);
    }

    return curr;
}

void dfsDist(int curr,int dist,int dept)
{
    v.push_back({dist,dept});
    ans=min1(ans,dept+best[k-dist]);
    for(auto i:edg[curr])
    {
        if(i.first==father[curr]||hasBeenCentr[i.first])continue;
        dfsDist(i.first,dist+i.second,dept+1);
    }
}

void centrDec(int curr)
{
    dfs(curr,-1);
    v.clear();
    int cen=centr(curr,pod[curr]);
    for(int i=0;i<MAXK;i++)best[i]=inf;
    best[0]=0;
    for(auto i:edg[cen])
    {
        if(hasBeenCentr[i.first])continue;
        dfsDist(i.first,0,0);
        for(auto t:v)best[t.first]=min1(best[t.first],t.second);
    }
    hasBeenCentr[cen]=1;
}

int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0;i<N-1;i++)
    {
        edg[H[i][0]].push_back({H[i][1],L[i]});
        edg[H[i][1]].push_back({H[i][0],L[i]});
    }

    centrDec(0);

    return ans;
}

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