Submission #964364

#	Time	Username	Problem	Language	Result	Execution time	Memory
964364		vjudge1	경주 (Race) (IOI11_race)	C++17	100 / 100	648 ms	41564 KiB

race

#include <bits/stdc++.h>

#ifdef DEBUG
    #include <debug.hpp>
#else
    #define debug(...) 42
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;

struct Solution {
    int n, k; 
    int ans = 1e9;
    vector<vector<pair<int, int>>> g;
    vector<int> sz, used; 

    Solution(int _n, int _k, int (*h)[2], int* l) : n(_n), k(_k) {
        g.assign(n, {});
        sz.assign(n, 0);
        used.assign(n, 0);
    
        for (int i = 0; i < n - 1; ++i) {
            g[h[i][0]].emplace_back(h[i][1], l[i]);
            g[h[i][1]].emplace_back(h[i][0], l[i]);
        }
    }

    int find_sz(int v, int p) {
        sz[v] = 1;
        for (auto [to, w] : g[v]) {
            if (used[to] || to == p) continue;
            sz[v] += find_sz(to, v);
        }
        return sz[v];
    }

    int centr(int v, int p, int cn) {
        bool flag = 1;
        while (flag) {
            flag = 0;
            for (auto [to, w] : g[v]) {
                if (used[to] || to == p) continue;
                if (sz[to] > cn / 2) {
                    p = v;
                    v = to;
                    flag = 1;
                    break;
                }
            }
        }
        return v;
    }
    
    void dfs(int v, int p, int d, int l, vector<pair<int, int>> &t) {
        t.emplace_back(d, l);
        for (auto [to, w] : g[v]) {
            if (used[to] || to == p) continue;
            dfs(to, v, d + w, l + 1, t);
        }
    } 

    void root_solve(int v, int vn) {
        unordered_map<int, int> d;
        d.reserve(vn);
        d[0] = 1;
        for (auto [to, w] : g[v]) {
            if (used[to]) continue;
            vector<pair<int, int>> t;
            t.reserve(sz[to]);
            dfs(to, v, w, 1, t);

            for (auto [x, y] : t) {
                if (k >= x && d[k - x] != 0) {
                    ans = min(ans, y + d[k - x] - 1);
                }
            }
            for (auto [x, y] : t) {
                if (d[x] == 0 || d[x] > y + 1) {
                    d[x] = y + 1;
                }
            }
        }
    }

    void decomp(int v) {
        int cn = find_sz(v, v);
        int c = centr(v, v, cn); 
        used[c] = 1;
        root_solve(c, cn);
        for (auto [to, w] : g[c]) {
            if (used[to]) continue;
            decomp(to);
        }
    }

    int solve() {
        decomp(0);
        return (ans == 1e9 ? -1 : ans);
    }
};

int best_path(int n, int k, int (*h)[2], int* l) {
    Solution sol(n, k, h, l);
    return sol.solve();
}   

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