Submission #347171

#	Time	Username	Problem	Language	Result	Execution time	Memory
347171		dolphingarlic	Factories (JOI14_factories)	C++14	15 / 100	8121 ms	248920 KiB

factories

#include "factories.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

set<pair<int, ll>> graph[500000];
int tin[500000], tout[500000], timer = 0, anc[500000][20];
ll to_anc[500000][20];
int subtree[500000], c_par[500000];
ll c_dist[500000];

void dfs(int node = 0, int parent = -1) {
    tin[node] = timer++;
    for (int i = 1; i < 20; i++) {
        anc[node][i] = anc[anc[node][i - 1]][i - 1];
        to_anc[node][i] = to_anc[node][i - 1] + to_anc[anc[node][i - 1]][i - 1];
    }
    for (pair<int, ll> i : graph[node]) if (i.first != parent) {
        anc[i.first][0] = node;
        to_anc[i.first][0] = i.second;
        dfs(i.first, node);
    }
    tout[node] = timer++;
}

bool is_ancestor(int u, int v) { return (tin[u] <= tin[v] && tout[u] >= tout[v]); }

ll dist(int u, int v) {
    ll ans = 0;
    for (int i = 19; ~i; i--) if (!is_ancestor(anc[u][i], v)) {
        ans += to_anc[u][i];
        u = anc[u][i];
    }
    if (!is_ancestor(u, v)) ans += to_anc[u][0];
    for (int i = 19; ~i; i--) if (!is_ancestor(anc[v][i], u)) {
        ans += to_anc[v][i];
        v = anc[v][i];
    }
    if (!is_ancestor(v, u)) ans += to_anc[v][0];
    return ans; 
}

void get_subtree_sizes(int node, int parent = -1) {
    subtree[node] = 1;
    for (pair<int, ll> i : graph[node]) if (i.first != parent) {
        get_subtree_sizes(i.first, node);
        subtree[node] += subtree[i.first];
    }
}

int get_centroid(int node, int parent, int tree_size) {
    for (pair<int, ll> i : graph[node])
        if (i.first != parent && subtree[i.first] > tree_size)
            return get_centroid(i.first, node, tree_size);
    return node;
}

void centroid_decomp(int node = 0, int prv_centroid = -1) {
    get_subtree_sizes(node);
    int centroid = get_centroid(node, -1, subtree[node] / 2);
    c_par[centroid] = prv_centroid;
    for (pair<int, ll> i : graph[centroid]) {
        graph[i.first].erase({centroid, i.second});
        centroid_decomp(i.first, centroid);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        graph[A[i]].insert({B[i], D[i]});
        graph[B[i]].insert({A[i], D[i]});
    }
    dfs();
    centroid_decomp();
    for (int i = 0; i < N; i++) c_dist[i] = LLONG_MAX / 2;
}

ll Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        int curr = X[i];
        while (curr != -1) {
            c_dist[curr] = min(c_dist[curr], dist(X[i], curr));
            curr = c_par[curr];
        }
    }
    ll ans = LLONG_MAX;
    for (int i = 0; i < T; i++) {
        int curr = Y[i];
        while (curr != -1) {
            ans = min(ans, c_dist[curr] + dist(Y[i], curr));
            curr = c_par[curr];
        }
    }
    for (int i = 0; i < S; i++) {
        int curr = X[i];
        while (curr != -1) {
            c_dist[curr] = LLONG_MAX / 2;
            curr = c_par[curr];
        }
    }
    return ans;
}

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