Submission #1110944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110944		LucasLe	Factories (JOI14_factories)	C++17	100 / 100	3036 ms	203200 KiB

factories

#include <bits/stdc++.h>

const int maxn = 5e5 + 5;
const int LG = 20;
const long long INF = 1e17;

int n, q, timeDfs;
int sparse[1000005][LG + 5], par[maxn + 5];
int lg[1000005], sz[maxn + 5], h[maxn + 5], tin[maxn + 5];

long long depth[maxn + 5], d[maxn + 5];

bool del[maxn + 5];

std::vector<int> nd;
std::vector<std::pair<int, int>> g[maxn + 5];

void init() {
    for (int i = 2; i <= 1000000; ++i)
        lg[i] = lg[i / 2] + 1;
}

int combine(int u, int v) {
    return h[u] < h[v] ? u : v;
}

void dfs(int u, int p) {
    sparse[++timeDfs][0] = u;
    tin[u] = timeDfs;
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        int w = tmp.second;
        if (v == p) continue;
        depth[v] = depth[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
        sparse[++timeDfs][0] = u; 
    }
}

int find_centroid(int u, int p, int m) {
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        if (del[v] || v == p) continue;
        if (sz[v] > m / 2) return find_centroid(v, u, m);
    }
    return u;
}

void reset_sz(int u, int p) {
    sz[u] = 1;
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        if (del[v] || v == p) continue;
        reset_sz(v, u);
        sz[u] += sz[v];
    }
}

long long dist(int u, int v) {
    if (tin[u] > tin[v]) std::swap(u, v);
    int base = lg[tin[v] - tin[u] + 1];
    int lca = combine(sparse[tin[u]][base], sparse[tin[v] - (1 << base) + 1][base]);
    return depth[u] + depth[v] - 2 * depth[lca];
}

int CD(int u) {
    reset_sz(u, 0);
    int cen = find_centroid(u, 0, sz[u]);
    del[cen] = true;
    for (std::pair<int, int> tmp : g[cen]) {
        int v = tmp.first;
        if (del[v]) continue;
        par[CD(v)] = cen;
    }
    return cen;
}

void update(int u) {
    int anc = u;
    while (anc) {
        d[anc] = std::min(d[anc], dist(u, anc));
        anc = par[anc];
    }
}

long long query(int u) {
    int anc = u;
    long long ans = INF;
    while (anc) {
        ans = std::min(ans, dist(u, anc) + d[anc]);
        anc = par[anc];
    }
    return ans;
}

void init_d(int u) {
    int anc = u;
    while (anc) {
        d[anc] = INF;
        anc = par[anc];
    }
} 

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i <= n - 2; ++i) {
        int u = A[i] + 1;
        int v = B[i] + 1;
        int w = D[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, 0);
    for (int j = 1; j <= LG; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= timeDfs; ++i) {
            sparse[i][j] = combine(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
        }
    }
    CD(1);
    init();
    for (int i = 1; i <= n; ++i) d[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        int u = X[i] + 1;
        nd.push_back(u);
        update(u);
    }
    long long ans = INF;
    for (int i = 0; i < T; ++i) {
        int u = Y[i] + 1;
        ans = std::min(ans, query(u));
    }
    for (int u : nd) 
        init_d(u);
    nd.clear();
    return ans;
}

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