제출 #48064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48064		TAMREF	경주 (Race) (IOI11_race)	C++11	100 / 100	1203 ms	34696 KiB

race

#include <bits/stdc++.h>
#include "race.h"

#define va first //정점
#define vb second //비용

using namespace std;

typedef pair<int,int> pii;

const int mxn = 200005, mxk = 1e6 + 5, inf = 1e9;

vector<pii> G[mxn];

int clk_dfs, clk_dnc;

int cnt[mxn], vis[mxn], par[mxn];

int del[mxn];

int dep[mxn];

int min_cnt[mxk], min_cnt_chk[mxk];

pii Q[mxn];
int q_f, q_r;

int N, K;
int ans = inf;

void dfsi(int v){
    cnt[v] = 1;
    vis[v] = clk_dfs;
    for(pii &p : G[v]){
        if(del[p.va] || vis[p.va] == clk_dfs) continue;
        dfsi(p.va);
        par[p.va] = v;
        cnt[v] += cnt[p.va];
    }
}

int get_cen(int v, int sz){
    for(pii &p : G[v]){
        if(del[p.va] || p.va == par[v]) continue;
        if(cnt[p.va] > sz/2) return get_cen(p.va, sz);
    }
    return v;
}

void dfs_race(int v, int sum){
    vis[v] = clk_dfs;
    Q[q_r++] = {sum, dep[v]}; //va = cost, vb = dep;
    for(pii &p : G[v]){
        if(del[p.va] || vis[p.va] == clk_dfs) continue;
        par[p.va] = v;
        dep[p.va] = dep[v] + 1;
        dfs_race(p.va, sum + p.vb);
    }
}

void dnc(int root){
    pii tmp;

    ++clk_dfs;
    dfsi(root);
    int cen = get_cen(root, cnt[root]);

    min_cnt[0] = 0; min_cnt_chk[0] = ++clk_dnc; //centroid itself!

    for(pii &p : G[cen]){
        if(del[p.va]) continue;
        q_f = q_r = 0;
        dep[p.va] = 1;

        vis[cen] = ++clk_dfs;
        dfs_race(p.va, p.vb);

        for(int i = q_f; i < q_r; i++){
            if(Q[i].va > K) continue;
            if(min_cnt_chk[K - Q[i].va] == clk_dnc){
                ans = min(ans, Q[i].vb + min_cnt[K - Q[i].va]);
            }
        }

        while(q_f != q_r){
            tmp = Q[q_f++];
            if(tmp.va > K) continue;
            if(min_cnt_chk[tmp.va] != clk_dnc || min_cnt[tmp.va] > tmp.vb){
                min_cnt_chk[tmp.va] = clk_dnc;
                min_cnt[tmp.va] = tmp.vb;
            }
        }
    }

    del[cen] = 1;
    for(pii &p : G[cen]){
        if(del[p.va]) continue;
        dnc(p.va);
    }
}

int best_path(int n, int k, int H[][2], int L[]){
    N = n;
    K = k;
    for(int i = 0; i < n-1; i++){
        G[H[i][0]].emplace_back(H[i][1], L[i]);
        G[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    dnc(1);
    return ans == inf ? -1 : ans;
}

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