Submission #1084141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084141		f0rizen	Factories (JOI14_factories)	C++17	100 / 100	2999 ms	236696 KiB

factories

#include "factories.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

struct Edge {
    int to, w;
};

vector<vector<Edge>> g;
vector<bool> used;
vector<int> sz, par;
vector<vector<ll>> dist;
vector<ll> closest;

void dfs_sz(int v, int p = -1) {
    sz[v] = 1;
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            dfs_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

void dfs_dist(int v, int p = -1, ll d = 0) {
    dist[v].push_back(d);
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            dfs_dist(u, v, d + w);
        }
    }
}

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

void build(int v, int p = -1) {
    dfs_sz(v);
    dfs_dist(v);
    par[v] = p;
    used[v] = 1;
    for (auto [u, w] : g[v]) {
        if (!used[u]) {
            build(centroid(u, v, sz[u]), v);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    g.resize(N);
    for (int i = 0; i < N - 1; ++i) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    used.resize(N);
    sz.resize(N);
    par.resize(N);
    dist.resize(N);
    dfs_sz(0);
    build(centroid(0, -1, sz[0]));
    closest.resize(N, infll);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        int v = X[i];
        int u = v;
        int j = (int) dist[v].size() - 1;
        while (u != -1) {
            closest[u] = min(closest[u], dist[v][j]);
            u = par[u];
            --j;
        }
    }
    ll ans = infll;
    for (int i = 0; i < T; ++i) {
        int v = Y[i];
        int u = v;
        int j = (int) dist[v].size() - 1;
        while (u != -1) {
            ans = min(ans, closest[u] + dist[v][j]);
            u = par[u];
            --j;
        }
    }
    for (int i = 0; i < S; ++i) {
        int v = X[i];
        int u = v;
        int j = (int) dist[v].size() - 1;
        while (u != -1) {
            closest[u] = infll;
            u = par[u];
            --j;
        }
    }
    return ans;
}

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