제출 #1228412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228412		countless	경주 (Race) (IOI11_race)	C++20	100 / 100	581 ms	54036 KiB

race

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

vector<bool> good;
vector<ll> sz;
vector<vector<pair<ll, ll>>> adj;

ll n, k;

void subtree(ll u, ll p = -1) {
    sz[u] = 1;
    for (auto &[v, ww] : adj[u]) {
        if (v != p and good[v]) {
            subtree(v, u);
            sz[u] += sz[v];
        }
    }
}

ll centroid(ll targ, ll u, ll p = -1) {
    for (auto &[v, ww] : adj[u]) {
        if (v != p and good[v] and 2 * sz[v] > targ) {
            return centroid(targ, v, u);
        }
    }

    return u;
}

void process(vector<pair<ll, ll>> &w, ll dist, ll cost, ll u, ll p = -1) {
    if (dist > k) return;

    w.push_back({dist, cost});

    for (auto &[v, ww] : adj[u]) {
        if (v != p and good[v]) {
            process(w, dist + ww, cost + 1, v, u);
        }
    }
}

ll dnc(ll st) {
    subtree(st);
    ll siz = sz[st];

    ll cen = centroid(siz, st);

    good[cen] = false;

    unordered_map<ll, vector<pair<ll, ll>>> mp;
    for (auto &[v, ww] : adj[cen]) {
        if (good[v]) {
            process(mp[v], ww, 1, v, cen);
        }
    }

    ll res = LLONG_MAX;
    unordered_map<ll, ll> rec;
    rec[0] = 0;
    
    for (auto &[v, ls] : mp) {
        for (auto &[d, c] : ls) {
            if (k - d >= 0 and rec.count(k - d)) {
                res = min(res, rec[k - d] + c);
            }
        }

        for (auto &[d, c] : ls) {
            if (rec.count(d)) rec[d] = min(rec[d], c);
            else rec[d] = c;
        }
    }

    for (auto &[v, ww] : adj[cen]) {
        if (good[v]) {
            res = min(res, dnc(v));
        }
    }

    return res;
}

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

    good.assign(n, true);
    sz.resize(n);
    ll ans = dnc(0);

    return (ans == LLONG_MAX ? -1 : ans);
}

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