제출 #1287170

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

race

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

typedef long long ll;

const int MAXN = 2e5;
const ll INFLL = 1e18;
const int INF = 1e9;

int mx[MAXN], subSz[MAXN], mnDepth[MAXN];
vector<pair<int, ll>> adj[MAXN];
int depth[MAXN];
ll depthW[MAXN], allDepthW[MAXN];
map<int, int> mpDepthW;
vector<int> sub[MAXN];

int n, k;
int ans = INF;

void dfsPre(int v, int pai) {
    subSz[v] = 1;
    allDepthW[v] = depthW[v];
    for (auto [viz, w] : adj[v]) {
        if (viz == pai) continue;
        depthW[viz] = depthW[v] + w;
        depth[viz] = depth[v] + 1;
        dfsPre(viz, v);
        if (mx[v] == -1 or subSz[viz] > subSz[mx[v]])
            mx[v] = viz;
        subSz[v] += subSz[viz];
    }
}

void add(int v, vector<int> newNodes) {
    for (int i : newNodes) {
        sub[v].push_back(i);
        int dep = mpDepthW[depthW[i]];
        mnDepth[dep] = min(mnDepth[dep], depth[i]);
    }
}

void dfs(int v, int pai, bool clear) {
    for (auto [viz, w] : adj[v]) {
        if (viz == pai or viz == mx[v]) continue;
        dfs(viz, v, true);
    }
    // cout << v << ':';
    // for (int i=0; i<n; i++) cout << mnDepth[i] << ' ';
    // cout << endl;
    if (mx[v] != -1) {
        dfs(mx[v], v, false);
        swap(sub[v], sub[mx[v]]);
    }

    if (mpDepthW.count(k + depthW[v]) != 0)
        ans = min(ans, mnDepth[mpDepthW[k+depthW[v]]] - depth[v]);

    add(v, {v});
    for (auto [viz, w] : adj[v]) {
        if (viz == pai or viz == mx[v]) continue;
        for (int i : sub[viz]) {
            ll x = depthW[i] - depthW[v];
            if (mpDepthW.count(k - x + depthW[v]) == 0) continue;
            ans = min(ans, depth[i] - depth[v] + mnDepth[mpDepthW[k-x + depthW[v]]] - depth[v]);
        }

        add(v, sub[viz]);
        sub[viz].clear();
    }
    // cout << v << ' ' << ans << '\n';

    if (clear) {
        for (int i : sub[v]) {
            mnDepth[mpDepthW[depthW[i]]] = INF;
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    for (int i=0; i<n; i++) {
        mnDepth[i] = INF;
        mx[i] = -1;
    }
    for (int i=0; i<n-1; i++) {
        int u = H[i][0], v = H[i][1]; ll w = L[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    dfsPre(0, -1);
    // for (int i=0; i<n; i++) cout << depthW[i] << ' ';
    // cout << '\n';

    sort(allDepthW, allDepthW + n);
    for (int i=0; i<n; i++) mpDepthW[allDepthW[i]] = i;

    dfs(0, -1, false);

    if (ans == INF) return -1;

    return ans;
}

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