제출 #446124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446124		Deepesson	Race (IOI11_race)	C++17	100 / 100	537 ms	103500 KiB

race

#include <bits/stdc++.h>
#define MAX 205000
typedef std::pair<int,int> pii;
int NA,KA;
std::vector<pii> con[MAX];
std::map<int,long long> mapa[MAX];
int prof[MAX];
int distancia[MAX];
long long count=1e6;
void merge(int a,int b) {
    if(mapa[a].size()<mapa[b].size())std::swap(mapa[a],mapa[b]);
    for(auto&x:mapa[b]){
        {
            auto it = mapa[a].find((KA-(x.first-distancia[a]))+distancia[a]);
            if(it!=mapa[a].end())count=std::min(count,it->second+x.second-(2*prof[a]));
        }
    }
    for(auto&x:mapa[b]){
        auto it = mapa[a].find(x.first);
        if(it==mapa[a].end())
            mapa[a][x.first]=x.second;
        else mapa[a][x.first]=std::min(x.second,mapa[a][x.first]);
    }
}
void dfs(int pos,int prev,int dist,int depth=0) {
    mapa[pos][dist]=depth;
    prof[pos]=depth;
    distancia[pos]=dist;
    for(auto&x:con[pos]){
        if(prev==x.first)continue;
        dfs(x.first,pos,dist+x.second,depth+1);
        merge(pos,x.first);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    for(auto&x:mapa)x.clear();
    for(auto&x:con)x.clear();
    NA=N;KA=K;
    for(int i=0;i!=N-1;++i){
        int a,b,c;
        a=H[i][0],b=H[i][1],c=L[i];
        con[a].push_back({b,c});
        con[b].push_back({a,c});
    }
    dfs(0,-1,0);
    if(count==1e6)count=-1;
    return count;
}

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