Submission #630160

#	Time	Username	Problem	Language	Result	Execution time	Memory
630160		bebra	Factories (JOI14_factories)	C++17	100 / 100	4164 ms	239532 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];
long long distances[MAX_N];


inline 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];
    }
}

inline 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;
}

inline 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);
        }
    }
}

inline void add_vertex(int v) {
    for (int c : centroids[v]) {
        distances[c] = min(distances[c], dist[level[c]][v]);
    }
}

inline void remove_vertex(int v) {
    for (int c : centroids[v]) {
        distances[c] = INF;
    }
}

inline long long get_closest(int v) {
    long long res = INF;
    for (int c : centroids[v]) {
        if (distances[c] != INF) {
            res = min(res, dist[level[c]][v] + distances[c]);
        }
    }
    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]);
    }
    fill_n(distances, MAX_N, INF);
    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: 67 / 67