Submission #387824

#	Time	Username	Problem	Language	Result	Execution time	Memory
387824		arujbansal	Factories (JOI14_factories)	C++17	100 / 100	6249 ms	363620 KiB

factories

#include "factories.h"

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

using ll = long long;

const int MXN = 5e5 + 1, MXK = 19;
const ll INF = 1e18;
vector<pair<int, ll>> g[MXN], par[MXN];
int subtree[MXN];
bool vis[MXN];
ll best[MXN];

void dfs1(int u, int p) {
    subtree[u] = 1;

    for (const auto &[v, w] : g[u]) {
        if (v == p) continue;

        dfs1(v, u);
        subtree[u] += subtree[v];
    }
}

void dfs2(int u, int p, int cur_centroid, ll cur_dist) {
    par[u].emplace_back(cur_centroid, cur_dist);

    for (const auto &[v, w] : g[u]) {
        if (v == p || vis[v]) continue;
        dfs2(v, u, cur_centroid, cur_dist + w);
    }
}

int centroid(int u, int p, int vertices) {
    if (p != -1) {
        subtree[p] -= subtree[u];
        subtree[u] += subtree[p];
    }

    for (const auto &[v, w] : g[u]) {
        if (v == p || vis[v]) continue;

        if (subtree[v] * 2 > vertices)
            return centroid(v, u, vertices);
    }

    return u;
}

void build_cd(int u, int p) {
    int c = centroid(u, -1, subtree[u]);

    if (p == -1)
        p = c;

    dfs2(c, -1, c, 0);
    vis[c] = true;

    for (const auto &[v, w] : g[c]) {
        if (vis[v]) continue;
        build_cd(v, c);
    }
}

void build_factory(int u) {
    best[u] = 0;

    for (const auto &[p, d] : par[u])
        best[p] = min(best[p], d);
}

void remove_factory(int u) {
    best[u] = INF;

    for (const auto &[p, d] : par[u])
        best[p] = INF;
}

ll query_factory(int u) {
    ll ans = best[u];

    for (const auto &[p, d] : par[u])
        ans = min(ans, best[p] + d);

    return ans;
}

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

    dfs1(0, -1);
    build_cd(0, -1);

    for (int i = 0; i <= N; i++)
        best[i] = INF;
}

ll Query(int S, int X[], int T, int Y[]) {
    ll ans = INF;

    for (int i = 0; i < S; i++)
        build_factory(X[i]);

    for (int i = 0; i < T; i++)
        ans = min(ans, query_factory(Y[i]));

    for (int i = 0; i < S; i++)
        remove_factory(X[i]);

    return ans;
}

#ifdef local
void solve() {
    int N,  Q;
    cin >> N >> Q;

    int A[N - 1], B[N - 1], D[N - 1];
    for (int i = 0; i < N - 1; i++)
        cin >> A[i] >> B[i] >> D[i];

    Init(N, A, B, D);

    while (Q--) {
        int S, T;
        cin >> S >> T;

        int X[S], Y[T];
        for (int i = 0; i < S; i++)
            cin >> X[i];

        for (int i = 0; i < T; i++)
            cin >> Y[i];

        cout << Query(S, X, T, Y) << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}
#endif

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