제출 #1268496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268496		enzy	경주 (Race) (IOI11_race)	C++20	100 / 100	339 ms	104228 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define ll long long
#define debug(args...) //fprintf(stderr, args)
using namespace std;
const int maxn=2e5+10;
const int inf=1e9+7;
vector<pair<int,ll>>v[maxn];
map<ll,ll>m[maxn];
ll prof[maxn], depth[maxn], k, resp=maxn;
void merge(int a, int b){
    debug("%d %d %lld\n", a, b, resp);
    bool swp=false;
    if(m[a].size()<m[b].size()) swap(m[a],m[b]);
    for(auto p : m[b]) if(m[a].count(k+2*prof[a]-p.first)) resp=min(resp,p.second+m[a][k+2*prof[a]-p.first]-2*depth[a]);
    for(auto p : m[b]){
        if(m[a].count(p.first)) m[a][p.first]=min(m[a][p.first],p.second);
        else m[a][p.first]=p.second;
    }
}
void dfs(int u, int pai){
    m[u][prof[u]]=depth[u];
    for(auto p : v[u]){
        int viz=p.first, w=p.second;
        if(viz==pai) continue;
        prof[viz]=prof[u]+w;
        depth[viz]=depth[u]+1;
        dfs(viz,u);
        merge(u,viz);
    }
}
int best_path(int n, int K, int H[][2], int L[]){
    k=K;
    for(int i=0;i<n-1;i++){
        H[i][0]++; H[i][1]++;
        v[H[i][0]].push_back({H[i][1],L[i]});
        v[H[i][1]].push_back({H[i][0],L[i]});
    }
    dfs(1,1);
    int ret=resp;
    if(resp==maxn) return -1;
    else return ret;
}

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