제출 #1291401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291401		MC123	경주 (Race) (IOI11_race)	C++20	0 / 100	7 ms	11320 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int MN=200100;
vector<pair<int,int>>r[MN];
int k;
unordered_map<int,int>um[MN];
int sz[MN],ans=INT_MAX,offset[MN],offet[MN];
void dfs(int x,int par){
    //cout<<x<<" "<<par<<"\n";
    sz[x]++;
    um[x][0]=1;
    //for(auto p:r[x]){
    //    cout<<p.first<<" "<<p.second<<"\n";
    //}
    for(auto p:r[x]){
        if(p.first==par)continue;
        dfs(p.first,x);
        offset[p.first]+=p.second;
        offet[p.first]+=1;
        if(sz[x]<sz[p.first]){
            swap(sz[x],sz[p.first]);
            swap(um[x],um[p.first]);
            swap(offset[x],offset[p.first]);
        }
        for(auto q:um[p.first]){
            if(um[x][k-(q.first+offset[p.first]+offset[x])]>0){
                ans=min(ans,um[x][k-(q.first+offset[p.first]+offset[x])]+q.second+offet[x]+offet[p.first]-2);
            }
        }
        for(auto q:um[p.first]){
            if(um[x][q.first+offset[p.first]-offset[x]]==0){
                sz[x]++;
                um[x][q.first+offset[p.first]-offset[x]]=q.second+offet[p.first]-offet[x];
            }else if(um[x][q.first+offset[p.first]-offset[x]]>q.second+offet[p.first]-offet[x]){
                um[x][q.first+offset[p.first]-offset[x]]=q.second+offet[p.first]-offet[x];
            }
        }
    }
}
int best_path(int n, int K, int h[][2], int l[]){
    for(int i=0;i<n-1;i++){
        r[h[i][0]].push_back({h[i][1],l[i]});
        r[h[i][1]].push_back({h[i][0],l[i]});
    }
    k=K;
    dfs(1,-1);
    if(ans==INT_MAX)ans=-1;
    return ans;
}

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