Submission #824421

#	Time	Username	Problem	Language	Result	Execution time	Memory
824421		Koyote	Factories (JOI14_factories)	C++14	0 / 100	434 ms	524288 KiB

factories

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

typedef long long ll;

const int N = 5e5 + 2;
const ll LINF = 1e18;

int n, subtree_size[N];
vector<pair<int, ll>> adj[N], ancestors[N];
bitset<N> removed;
ll min_dist_from_source[N];

int dfs_subtree_size(int u, int p, ll depth, int anc) {
    subtree_size[u] = 1;
    if (anc != -1) ancestors[u].emplace_back(anc, depth);
    for (auto v : adj[u]) if (!removed[v.first] && v.first != p)
        subtree_size[u] += dfs_subtree_size(v.first, u, depth + v.second, anc);
    return subtree_size[u];
}

int find_centroid(int u, int p, int subt_sz) {
    for (auto v : adj[u]) if (v.first != p && subtree_size[v.first] > subt_sz / 2)
        return find_centroid(v.first, u, subt_sz);
    return u;
}

void centroid_decompose(int u) {
    int c = find_centroid(u, -1, subtree_size[u]);
    removed[c] = 1;
    for (auto v : adj[c]) if (!removed[v.first])
        dfs_subtree_size(v.first, -1, v.second, c);
    for (auto v : adj[c]) if (!removed[v.first])
        centroid_decompose(v.first);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n; i++) min_dist_from_source[i] = LINF;
    for (int i = 0; i < n - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }

    dfs_subtree_size(0, -1, 0, -1);
    centroid_decompose(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll res = LINF;
    for (int i = 0; i < S; i++) {
        int u = X[i]; min_dist_from_source[u] = 0;
        for (auto v : ancestors[u])
            min_dist_from_source[v.first] = min(min_dist_from_source[v.first], v.second);
    }
    for (int i = 0; i < T; i++) {
        int u = Y[i];
        res = min(res, min_dist_from_source[u]);
        for (auto v : ancestors[u])
            res = min(res, min_dist_from_source[v.first] + v.second);
    }
    for (int i = 0; i < S; i++) {
        int u = X[i]; min_dist_from_source[u] = LINF;
        for (auto v : ancestors[u])
            min_dist_from_source[v.first] = LINF;
    }
    return res;
}

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