제출 #1170772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170772		nguyenkhangninh99	Race (IOI11_race)	C++17	100 / 100	288 ms	76292 KiB

race

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = 1e6 + 5;

ll d[maxn], h[maxn];
vector<pair<int, int>> g[maxn];
ll ans = 1e9;
int n, k;

void dfs0(int u, int p){
    for(auto [v, w]: g[u]){
        if(v == p) continue;
        d[v] = d[u] + w;
        h[v] = h[u] + 1;
        dfs0(v, u);
    }
}


void merge(map<ll, ll> &a, map<ll, ll> &b, ll rh, ll rd){
    if((int)a.size() < (int)b.size()) swap(a , b);

    for(auto [v1, v2]: b){
        if(a.count(k - v1 + 2 * rd)) ans = min(ans, a[k - v1 + 2 * rd] + v2 - 2 * rh);
    }

    for(auto [v1, v2]: b){
        if(a.count(v1)) a[v1] = min(a[v1], v2);
        else a[v1] = v2;
    }

    if(a.count(k + rd)) ans = min(ans, a[k + rd] - rh);
}

map<ll, ll> dfs(int u, int p){
    map<ll, ll> res;
    res[d[u]] = h[u];

    for(auto [v, w]: g[u]){
        if(v == p) continue;
        map<ll, ll> f = dfs(v, u);
        merge(res, f, h[u], d[u]);
    }
    return res;
}


int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;

    for(int i = 0; i < n - 1; i++){
        int u = H[i][0], v = H[i][1], w = L[i];
        g[++u].push_back({++v, w});
        g[v].push_back({u, w});
    }

    dfs0(1, 1);
    dfs(1, 1);

    if(ans > n) return -1;
    return ans;
}

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