Submission #1185988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185988		g4yuhg	Factories (JOI14_factories)	C++17	100 / 100	2821 ms	356372 KiB

factories

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

typedef long long ll;
#define pii pair<ll, ll>
const int N = 500005;
const ll INF = 1e18;

vector<pii> adj[N];
int del[N], child[N];
ll high[N], dist[N], min_dist[N];
vector<pii> par[N];

void cnt_child(int u, int parent) {
    child[u] = 1;
    for (auto &v : adj[u]) {
        if (v.first == parent || del[v.first]) continue;
        cnt_child(v.first, u);
        child[u] += child[v.first];
    }
}

int get_centroid(int u, int parent, int total) {
    for (auto &v : adj[u]) {
        if (v.first == parent || del[v.first]) continue;
        if (child[v.first] > total / 2)
            return get_centroid(v.first, u, total);
    }
    return u;
}

void dfs(int u, int parent, int root) {
    par[u].emplace_back(root, dist[u]);
    for (auto &v : adj[u]) {
        if (v.first == parent || del[v.first]) continue;
        high[v.first] = high[u] + 1;
        dist[v.first] = dist[u] + v.second;
        dfs(v.first, u, root);
    }
}

void build_centroid(int u) {
    cnt_child(u, -1);
    int c = get_centroid(u, -1, child[u]);
    high[c] = dist[c] = 0;
    dfs(c, -1, c);
    del[c] = 1;
    for (auto &v : adj[c]) {
        if (!del[v.first])
            build_centroid(v.first);
    }
}

void Init(int n, int A[], int B[], int D[]) {
    for (int i = 0; i < n - 1; i++) {
        int u = A[i], v = B[i], w = D[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    build_centroid(0);
    for (int i = 0; i < n; i++) {
        min_dist[i] = INF;
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> temp;  // lưu lại các đỉnh được cập nhật để khôi phục sau

    for (int i = 0; i < S; i++) {
        int u = X[i];
        for (auto &p : par[u]) {
            min_dist[p.first] = min(min_dist[p.first], p.second);
            temp.push_back(p.first);
        }
    }

    ll res = INF;
    for (int i = 0; i < T; i++) {
        int u = Y[i];
        for (auto &p : par[u]) {
            res = min(res, p.second + min_dist[p.first]);
        }
    }

    for (int x : temp) {
        min_dist[x] = INF;  // khôi phục lại
    }

    return res;
}

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