제출 #1218674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218674		a.pendov	경주 (Race) (IOI11_race)	C++20	0 / 100	39 ms	10568 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=10000009;
const long long MAXN=100009;
const long long MAXK=1000009;
vector<pair<int,int>> edg[MAXN];
long long pod[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)
{
    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,int f)
{
    for(auto i:edg[curr])
    {
        if(i.first==f||hasBeenCentr[i.first])continue;
        if(pod[i.first]>sz/2)return centr(i.first,sz,curr);
    }

    return curr;
}

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

void centrDec(int curr)
{
    dfs(curr,-1);
    v.clear();
    int cen=centr(curr,pod[curr],-1);
    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,i.second,1,cen);
        for(auto t:v)best[t.first]=min1(best[t.first],t.second);
    }
    hasBeenCentr[cen]=1;
    for(auto i:edg[cen])
    {
        if(hasBeenCentr[i.first])continue;
        centrDec(i.first);
    }
}

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);
    if(ans==inf)return -1;
    return ans;
}

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