제출 #824752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
824752		ma_moutahid	경주 (Race) (IOI11_race)	C++17	9 / 100	1105 ms	262144 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using ll =long long;
//#define int ll
ll LINF=1000000000000000000;
int INF=1e9;
#define pi pair<int,int>
#define pl pair<ll,ll>
#define endl '\n'
#define vi vector<int>
#define vii vector<vector<int>>
#define vl vector<ll>
#define vll vector<vector<ll>>
//#define int ll
using namespace std;
vector<vector<pi>>g;
int k;
int minimum=INF;

vi vinf={INF,-1};


void add(vector<vii>&v,vector<vii>&cv,int node,int dist){
    for(int i=0;i+dist<k+1;i++){
        if(v[i+dist][0][0]>cv[i][1][0]+1){
            v[i+dist][0][0]=cv[i][1][0]+1;
            v[i+dist][0][1]=node;
            if(v[i+dist][0][0]<v[i+dist][1][0]){
                swap(v[i+dist][0][0],v[i+dist][1][0]);
                swap(v[i+dist][0][1],v[i+dist][1][1]);
            }
        }
    }
}

vector<vii> dfs(int node,int parent){
    vector<vii>v(k+1,vii(2,vi({INF,-1})));
    v[0][1]={0,node};
    for(pi child:g[node]){
        if(child.first==parent)continue;
        auto cv=dfs(child.first,node);
        add(v,cv,child.first,child.second);
        cv.clear();
    }
    for(int i=0;i<k+1;i++){
        if(v[i][1][0]!=INF){
            if(v[k-i][1][0]!=INF){
                if(v[k-i][1][1]!=v[i][1][1]){
                    minimum=min(minimum,v[k-i][1][0]+v[i][1][0]);
                }
                else {
                    minimum=min(minimum,v[k-i][0][0]+v[i][1][0]);
                }
            }
        }
    }
    return v;
}


int best_path(int N, int K, int H[][2], int L[])
{
    g.resize(N);
    k=K;
    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]));
    }
    dfs(0,-1);


    if(minimum==1e9)return -1;
    return minimum;
}

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