제출 #1277635

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

race

#include "bits/stdc++.h"

using namespace std;
#define ll  long long

struct centroid {
    int n, k;
    vector<vector<pair<int, int>>> adj;
    vector<int> siz, is_removed;
    map<ll, int> mp;
    int ans = n + 1;

    centroid(int n, int k, vector<vector<pair<int, int>>> adj) : n(n), k(k), adj(adj), siz(n + 1), is_removed(n + 1) {
        decomp(0);
        if (ans == n + 1)
            ans = -1;
    }

    void dfs_size(int i, int p) {
        siz[i] = 1;
        for (auto &[it, d]: adj[i])
            if (it != p and !is_removed[it]) {
                dfs_size(it, i);
                siz[i] += siz[it];
            }
    }

    int get_centroid(int i, int p, int tot) {
        for (auto &[it, d]: adj[i])
            if (it != p and !is_removed[it])
                if (siz[it] * 2 > tot)
                    return get_centroid(it, i, tot);
        return i;
    }

    void get_ans(int i, int p, ll dist, int d) {
        if (dist > k)return;
        if (mp.count(k - dist))
            ans = min(ans, mp[k - dist] + d);
        for (auto &[it, c]: adj[i])
            if (it != p and !is_removed[it])
                get_ans(it, i, dist + c, d + 1);

    }

    void dfs(int i, int p, ll dist, int d) {
        if (dist > k)return;
        if (!mp.count(dist))
            mp[dist] = d;
        else
            mp[dist] = min(mp[dist], d);
        for (auto &[it, c]: adj[i])
            if (it != p and !is_removed[it])
                dfs(it, i, dist + c, d + 1);

    }

    void decomp(int i) {
        dfs_size(i, i);
        int cent = get_centroid(i, i, siz[i]);
        mp[0] = 0;
        for (auto &[it, c]: adj[cent])
            if (!is_removed[it]) {
                get_ans(it, cent, c, 1);
                dfs(it, cent, c, 1);
            }

        mp.clear();
        is_removed[cent] = 1;
        for (auto &[it, d]: adj[cent])
            if (!is_removed[it])
                decomp(it);

    }


};

int best_path(int N, int K, int H[][2], int L[]) {
    int n = N;
    int k = K;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int g = 0; g < n - 1; g++) {
        int a = H[g][0], b = H[g][1], c = L[g];
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    centroid cn(n, k, adj);
    return cn.ans;
}

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