제출 #1292180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292180		tab1540	경주 (Race) (IOI11_race)	C++20	0 / 100	6 ms	9784 KiB

race

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

long long n, m;
vector<pair<int, int>> graph[200009];

long long prefix[200009];

int node2disc[200009];
int disc2node[400009];
int disc2dept[400009];
int cnt = 0;
void dfs1(int a, int par, int dept) {
    node2disc[a] = ++cnt;
    disc2node[cnt] = a;
    disc2dept[cnt] = dept;

    for (pair<int, int> x : graph[a]) {
        if (x.first == par) continue;

        prefix[x.first] = prefix[a] + x.second;
        dfs1(x.first, a, dept + 1);
        disc2node[cnt] = a;
        disc2dept[cnt] = dept;
    }
    cnt++;
}
pair<int, int> rmmq[400009][19];
void build_rmq() {
    for (int i = 1; i < cnt; i++) {
        rmmq[i][0] = {disc2dept[i], i};
        for (int j = 0; (1 << (j + 1)) <= i; j++) {
            rmmq[i][j + 1] = min(rmmq[i - (1 << j)][j], rmmq[i][j]);
        }
    }
}
pair<int, int> get_rmq(int u, int v) {
    if (u == v) return rmmq[u][0];
    if (u > v) swap(u, v);
    int lg = 31 - __builtin_clz(v - u + 1);
    return min(
        rmmq[u + (1 << lg) - 1][lg],
        rmmq[v][lg]
    );
}
int get_lca(int u, int v) {
    return disc2node[get_rmq(node2disc[u], node2disc[v]).second];
}
int calc_dist(int u, int v) {
    return prefix[u] + prefix[v] - (2 * prefix[get_lca(u, v)]);
}
int calc_cnt_dist(int u, int v) {
    return disc2dept[node2disc[u]] + disc2dept[node2disc[v]] - (2 * get_rmq(node2disc[u], node2disc[v]).first);
}

int centroid_parent[200009] = {};

bool blocked[200009] = {};

int get_tree_size(int a, int par) {
    int sum = 1;
    for (pair<int, int> x : graph[a]) {
        if (x.first == par|| blocked[x.first]) continue;
        sum += get_tree_size(x.first, a);
    }
    return sum;
}

int get_centroid(int a, int par, int size) {
    int sum = 1;
    for (pair<int, int> x : graph[a]) {
        if (x.first == par || blocked[x.first]) continue;
        int ehe = get_centroid(x.first, a, size);
        if (ehe < 0) return ehe;
        sum += ehe;
    }
    if (sum > size / 2) return -a;
    return sum;
}

int build_centroid_tree(int a) {
    int centroid = -get_centroid(a, a, get_tree_size(a, a));
    // cout << a << " = " << centroid << " " << get_tree_size(a, a) << endl;

    blocked[centroid] = 1;

    for (pair<int, int> x : graph[centroid]) {
        if (blocked[x.first]) continue;

        int ch = build_centroid_tree(x.first);
        centroid_parent[ch] = centroid;
        // cout << ch << " " << centroid << endl;
    }
    return centroid;
}

map<long long, int> dist_to_child[200009];

int ans = 1 << 30;

void query(int a) {
    int gay = a;
    while (gay > 0) {
        int dist = calc_dist(gay, a);
        int cnt = calc_cnt_dist(gay, a);

        if (dist_to_child[gay].find(m - dist) != dist_to_child[gay].end()) {
            ans = min(ans, dist_to_child[gay][m - dist] + cnt);
        }

        if (dist_to_child[gay].find(dist) == dist_to_child[gay].end()) {
            dist_to_child[gay][dist] = cnt;
        } else {
            dist_to_child[gay][dist] = min(dist_to_child[gay][dist], cnt);
        }

        gay = centroid_parent[gay];
    }
}

int best_path(int nn, int mm, int edges[][2], int len[]) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie();

    n = nn;
    m = mm;

    for (int i = 0; i < n - 1; i++) {
        int x, y, z;
        x = edges[i][0] + 1;
        y = edges[i][1] + 1;
        z = len[i];

        graph[x].push_back({y, z});
        graph[y].push_back({x, z});
    }

    dfs1(1, 1, 1);
    build_rmq();
    build_centroid_tree(1);

    for (int i = 1; i <= n; i++) {
        query(i);
    }  

    if (ans == 1 << 30) {
        return -1;
    }

    return ans;
}

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