제출 #1151288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151288		Shadow1	Race (IOI11_race)	C++20	100 / 100	316 ms	81288 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
int n,k;
 
vector<pair<int,int>> al[200005];
pair<int,int> offset[200005];
map<int,int> s[200005];
 
int ans=1000000;
 
void dfs(int i,int p){
    s[i][0]=0;
 
    for (auto [it,w]:al[i]){
        if (it==p) continue;
        
        dfs(it,i);
        offset[it].first+=w;
        offset[it].second++;
        
        if (s[it].size()>s[i].size()){
            swap(s[it],s[i]);
            swap(offset[it],offset[i]);
        }
 
        for (auto x:s[it]){
            int t=k-x.first-offset[i].first-offset[it].first;
            if (s[i].count(t)) ans=min(ans,s[i][t]+offset[i].second+x.second+offset[it].second);
        }
 
        for (auto x:s[it]){
            int t=x.first+offset[it].first-offset[i].first;
            if (s[i].count(t)) s[i][t]=min(s[i][t],x.second+offset[it].second-offset[i].second);
            else s[i][t]=x.second+offset[it].second-offset[i].second;
        }
    }
}
 
int best_path(int N, int K, int h[][2], int l[]){
    n=N,k=K;
    for (int x=0;x<n-1;x++){
        al[h[x][0]].push_back({h[x][1],l[x]});
        al[h[x][1]].push_back({h[x][0],l[x]});
    }
 
    dfs(0,-1);
    return (ans==1000000)?-1:ans;
}

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