Submission #672390

#	Time	Username	Problem	Language	Result	Execution time	Memory
672390		vjudge1	Race (IOI11_race)	C++17	100 / 100	1846 ms	61932 KiB

race

#include "race.h"
#include <bits/stdc++.h>

#define el '\n'

typedef long long ll;
typedef long double ld;

using namespace std;

const int INF = 1e9;

struct Centroid {
    vector<bool> vis;
    map<ll, int> paths;
    vector<int> sz, par;
    vector<pair<ll, int>> dis;
    vector<vector<pair<int, int>>> g;

    Centroid(const vector<vector<pair<int, int>>> &g) : g(g) {
        sz.resize(g.size());
        vis.resize(g.size());
        par.resize(g.size());
    }

    int dfsSz(int u, int p) {
        sz[u] = 1;

        for (auto v: g[u]) {
            if (v.first == p || vis[v.first])
                continue;

            sz[u] += dfsSz(v.first, u);
        }

        return sz[u];
    }

    int dfsCentroid(int u, int p, int n) {
        for (auto v: g[u]) {
            if (v.first == p || vis[v.first])
                continue;

            if (sz[v.first] > n / 2)
                return dfsCentroid(v.first, u, n);
        }

        return u;
    }

    void dfs(int u, int p, int cur, ll curDis) {
        dis.emplace_back(curDis, cur);

        for (auto v: g[u]) {
            if (v.first == p || vis[v.first])
                continue;

            dfs(v.first, u, cur + 1, curDis + v.second);
        }
    }

    int build(int u, int p, int &k) {
        int centroid = dfsCentroid(u, p, dfsSz(u, p));

        if (p == -1)
            p = centroid;

        par[centroid] = p;

        vis[centroid] = 1;

        int ret = INF;

        for (auto v: g[centroid]) {
            if (vis[v.first])
                continue;

            dis.clear();

            dfs(v.first, centroid, 1, v.second);

            for (auto i: dis) {
                if (k == i.first || paths[k - i.first])
                    ret = min(ret, i.second + paths[k - i.first]);
            }

            for (auto i: dis) {
                if (!paths[i.first])
                    paths[i.first] = i.second;

                paths[i.first] = min(paths[i.first], i.second);
            }
        }

        paths.clear();

        for (auto v: g[centroid]) {
            if (vis[v.first])
                continue;

            ret = min(ret, build(v.first, centroid, k));
        }

        return ret;
    }
};

int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pair<int, int>>> g(N + 1);
    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]);
    }

    Centroid c(g);

    int sol = c.build(1, -1, K);

    return (sol == INF ? -1 : sol);
}

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