제출 #484190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484190		FEDIKUS	경주 (Race) (IOI11_race)	C++17	100 / 100	396 ms	78268 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define xx first
#define yy second

using namespace std;

const int maxn=2e5+10;

vector<pair<int,int> > g[maxn];
pair<pair<int,int> ,map<int,int> > s[maxn];

int merges(pair<pair<int,int> ,map<int,int> > &a,pair<pair<int,int> ,map<int,int> > &b,int c,int k){
    b.xx.xx+=c;
    b.xx.yy+=1;
    if(a.yy.size()<b.yy.size()) swap(a,b);
    int ret=INT_MAX;
    for(auto &i:b.yy){
        if(a.yy.find(k-i.xx-b.xx.xx-a.xx.xx)!=a.yy.end())
            ret=min(ret,a.yy[k-i.xx-b.xx.xx-a.xx.xx]+a.xx.yy+i.yy+b.xx.yy);
    }
    for(auto &i:b.yy){
        if(a.yy.find(i.xx+b.xx.xx-a.xx.xx)!=a.yy.end())
            a.yy[i.xx+b.xx.xx-a.xx.xx]=min(a.yy[i.xx+b.xx.xx-a.xx.xx],i.yy+b.xx.yy-a.xx.yy);
        else
            a.yy[i.xx+b.xx.xx-a.xx.xx]=i.yy+b.xx.yy-a.xx.yy;
    }
    return ret;
}

int dfs(int cvor,int k,int p=-1){
    int ret=INT_MAX;
    for(pair<int,int> i:g[cvor]){
        if(i.xx==p) continue;
        ret=min(ret,dfs(i.xx,k,cvor));
        ret=min(ret,merges(s[cvor],s[i.xx],i.yy,k));
    }
    s[cvor].yy[-s[cvor].xx.xx]=-s[cvor].xx.yy;
    if(s[cvor].yy.find(k-s[cvor].xx.xx)!=s[cvor].yy.end())
        ret=min(ret,s[cvor].yy[k-s[cvor].xx.xx]+s[cvor].xx.yy);
    return ret;
}

int best_path(int n, int k, int h[][2], int l[]){
    for(int i=0;i<n-1;i++){
        g[h[i][0]].push_back(make_pair(h[i][1],l[i]));
        g[h[i][1]].push_back(make_pair(h[i][0],l[i]));
    }
    int ret=dfs(0,k);
    return ret==INT_MAX ? -1:ret;
}

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