Submission #1287179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287179		gustavo_d	경주 (Race) (IOI11_race)	C++17	9 / 100	3092 ms	38160 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<ll, int> mpDepthW;
vector<int> sub[MAXN];

int n; ll 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);
    }

    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]);
    }

    if (clear) {
        for (int i=0; i<n; i++) mnDepth[i] = INF;
        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 << depth[i] << ' ' << depthW[i] << '\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