제출 #310876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310876		lohacho	경주 (Race) (IOI11_race)	C++14	21 / 100	3068 ms	49008 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const LL MOD = (LL)1e9 + 7;
const LL NS = (LL)2e5 + 4;
LL N, k;
vector<pair<LL, LL>> way[NS];
LL chk[NS], sz[NS], rt;
LL dis[(LL)1e6 + 4];
LL ans;
vector<LL> did;
vector<pair<LL, LL>> put;

void getroot(LL now, LL pr, LL alls){
    sz[now] = 1;
    LL f = 1;
    for(auto&nxt:way[now]){
        if(nxt.first == pr || chk[nxt.first]){
            continue;
        }
        getroot(nxt.first, now, alls);
        sz[now] += sz[nxt.first];
        if(sz[nxt.first] > alls / 2){
            f = 0;
        }
    }
    if(f){
        rt = now;
    }
}

void getdis(LL now, LL ndis, LL pr, LL ndep){
    LL need = k - ndis;
    if(need >= 0 && need < (int)1e6 + 4){
        ans = min(ans, ndep + dis[need]);
    }
    for(auto&nxt:way[now]){
        if(nxt.first == pr || chk[nxt.first]){
            continue;
        }
        getdis(nxt.first, ndis + nxt.second, now, ndep + 1);
    }
    if(ndis < (LL)1e6 + 4){
        if(dis[ndis] > ndep){
            put.push_back({ndis, ndep});
            did.push_back(ndis);
        }
    }
}

void sol(LL now, LL alls){
    dis[0] = 0;
    chk[now] = 1;
    did.clear();
    for(LL i = 0; i < (LL)way[now].size(); ++i){
        if(chk[way[now][i].first]){
            continue;
        }
        getdis(way[now][i].first, way[now][i].second, now, 1);
        while((LL)put.size()){
            dis[put.back().first] = min(dis[put.back().first], put.back().second);
            put.pop_back();
        }
    }
    while((LL)did.size()){
        dis[did.back()] = MOD;
        did.pop_back();
    }
    for(auto&nxt:way[now]){
        if(chk[nxt.first]){
            continue;
        }
        LL nsz = (sz[nxt.first] > sz[now] ? alls - sz[now]:sz[nxt.first]);
        getroot(nxt.first, now, nsz);
        sol(rt, nsz);
    }
}


int best_path(int n, int K, int H[][2], int L[])
{
    for(LL i = 0; i < (LL)1e6 + 4; ++i){
        dis[i] = MOD;
    }
    ans = MOD;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    N = n, k = K;
    for(LL i = 0; i < N - 1; ++i){
        LL a, b, c;
        a = H[i][0], b = H[i][1], c = L[i];
        way[a].push_back({b, c}), way[b].push_back({a, c});
    }
    getroot(1, -1, N);
    sol(rt, N);
    if(ans == MOD){
        return -1;
    }
    else{
        return ans;
    }
}

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