제출 #630158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
630158		bebra	공장들 (JOI14_factories)	C++17	33 / 100	8038 ms	259232 KiB

factories

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

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 500'000;
const int MAX_LOG = 20;
const long long INF = 1e16;
vector<pair<int, int>> g[MAX_N];

int sz[MAX_N];
int level[MAX_N];
bool used[MAX_N];
long long dist[MAX_LOG][MAX_N];
vector<int> centroids[MAX_N];
multiset<long long> distances[MAX_N];


void dfs_calc(int v, int p, int curr_weight, int c) {
    sz[v] = 1;
    if (c != -1) {
        dist[level[c]][v] = dist[level[c]][p] + curr_weight;
        centroids[v].push_back(c);
    }
    for (const auto& [u, weight] : g[v]) {
        if (used[u] || u == p) continue;
        dfs_calc(u, v, weight, c);
        sz[v] += sz[u];
    }
}

int find_centroid(int v, int p, int n) {
    for (const auto& [u, w] : g[v]) {
        if (used[u] || u == p) continue;
        if (2 * sz[u] > n) {
            return find_centroid(u, v, n);
        }
    }
    return v;
}

void dfs_build(int v = 0, int p = -1, int curr_weight = -1) {
    dfs_calc(v, p, curr_weight, p);
    int c = find_centroid(v, -1, sz[v]);
    if (p != -1) level[c] = level[p] + 1;
    centroids[c].push_back(c);
    used[c] = true;
    for (const auto& [u, weight] : g[c]) {
        if (!used[u]) {
            dfs_build(u, c, weight);
        }
    }
}

void add_vertex(int v) {
    for (int c : centroids[v]) {
        distances[c].insert(dist[level[c]][v]);
    }
}

void remove_vertex(int v) {
    for (int c : centroids[v]) {
        distances[c].erase(distances[c].find(dist[level[c]][v]));
    }
}

long long get_closest(int v) {
    long long res = INF;
    for (int c : centroids[v]) {
        if (!distances[c].empty()) {
            res = min(res, dist[level[c]][v] + *distances[c].begin());
        }
    }
    return res;
}

void Init(int n, int a[], int b[], int d[]) {
    for (int i = 0; i < n - 1; ++i) {
        int u = a[i];
        int v = b[i];
        g[u].emplace_back(v, d[i]);
        g[v].emplace_back(u, d[i]);
    }
    dfs_build();
}

long long Query(int n, int x[], int m, int y[]) {
    for (int i = 0; i < n; ++i) {
        add_vertex(x[i]);
    }
    long long res = INF;
    for (int i = 0; i < m; ++i) {
        res = min(res, get_closest(y[i]));
    }
    for (int i = 0; i < n; ++i) {
        remove_vertex(x[i]);
    }
    return res;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67