제출 #405654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405654		danielcm585	경주 (Race) (IOI11_race)	C++14	100 / 100	1740 ms	44704 KiB

race

#include "race.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef pair<int,int> ii;

const int INF = 1e9;
int ans, k;
vector<int> sz, dis, dep;
vector<bool> vis;
vector<vector<ii>> adj;
map<int,int> len, tmp;

void dfs(int cur, int par) {
    sz[cur] = 1;
    for (auto nx : adj[cur]) {
        if (nx.fi == par || vis[nx.fi]) continue;
        dfs(nx.fi,cur);
        sz[cur] += sz[nx.fi];
    }
}

int centroid(int cur, int par, int sub) {
    for (auto nx : adj[cur]) {
        if (nx.fi == par || vis[nx.fi]) continue;
        if (sz[nx.fi]*2 > sub) return centroid(nx.fi,cur,sub);
    }
    return cur;
}

void getLength(int cur, int par) {
    if (!tmp.count(dis[cur])) tmp[dis[cur]] = dep[cur];
    else tmp[dis[cur]] = min(tmp[dis[cur]],dep[cur]);
    for (auto nx : adj[cur]) {
        if (nx.fi == par || vis[nx.fi]) continue;
        dis[nx.fi] = dis[cur]+nx.se;
        dep[nx.fi] = dep[cur]+1;
        getLength(nx.fi,cur);
    }
}

void solve(int cur) {
    len.clear(); 
    len[0] = dis[cur] = dep[cur] = 0;
    for (auto nx : adj[cur]) {
        if (vis[nx.fi]) continue;
        tmp.clear(); 
        dis[nx.fi] = nx.se;
        dep[nx.fi] = 1;
        getLength(nx.fi,cur);
        // cout << nx.fi << " -> ";
        for (auto i : tmp) {
            // cout << i.fi << ' ';
            if (len.count(k-i.fi)) ans = min(ans,i.se+len[k-i.fi]);
        }
        // cout << '\n';
        for (auto i : tmp) {
            if (!len.count(i.fi)) len[i.fi] = i.se;
            else len[i.fi] = min(len[i.fi],i.se);
        }
    }
}

void DnC(int cur) {
    dfs(cur,-1);
    cur = centroid(cur,-1,sz[cur]);
    // cout << cur << " --------------\n";
    vis[cur] = 1;
    solve(cur);
    for (auto nx : adj[cur]) {
        if (vis[nx.fi]) continue;
        DnC(nx.fi);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    adj = vector<vector<ii>>(N);
    for (int i = 0; i < N-1; i++) {
        adj[H[i][0]].push_back(ii(H[i][1],L[i]));
        adj[H[i][1]].push_back(ii(H[i][0],L[i]));
    }
    k = K, ans = INF;
    vis = vector<bool>(N,0);
    sz = dis = dep = vector<int>(N);
    DnC(1);
    if (ans == INF) return -1;
    return ans;
}

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