Submission #541186

#	Time	Username	Problem	Language	Result	Execution time	Memory
541186		Jomnoi	Factories (JOI14_factories)	C++17	100 / 100	4066 ms	179088 KiB

factories

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

const int N = 5e5 + 10;
const long long INF = 1e18 + 7;

vector <pair <int, int>> adj[N];

// Centroid Decomposition
int sz[N], ancestor[N], level[N];
long long dist[N][20];
long long min_dist[N];
bool processed[N];

int find_size(int u, int p) {
    sz[u] = 1;
    for(auto [v, w] : adj[u]) {
        if(v == p or processed[v] == true) {
            continue;
        }

        sz[u] += find_size(v, u);
    }
    return sz[u];
}

int find_centroid(int u, int p, int n) {
    for(auto [v, w] : adj[u]) {
        if(v == p or processed[v] == true) {
            continue;
        }

        if(sz[v] > n/2) {
            return find_centroid(v, u, n);
        }
    }
    return u;
}

void get_distance(int u, int p, int l) {
    for(auto [v, w] : adj[u]) {
        if(v == p or processed[v] == true) {
            continue;
        }

        dist[v][l] = dist[u][l] + w;
        get_distance(v, u, l);
    }
}

void build_centroid(int u, int p) {
    int c = find_centroid(u, -1, find_size(u, -1));
    ancestor[c] = p;
    processed[c] = true;
    level[c] = level[p] + 1;

    get_distance(c, -1, level[c]);
    for(auto [v, w] : adj[c]) {
        if(processed[v] == true) {
            continue;
        }

        build_centroid(v, c);
    }
}

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

    build_centroid(1, 0);
    for(int i = 1; i <= N; i++) {
        min_dist[i] = INF;
    }
}

void reset(int u) {
    int a = u;
    while(a != 0) {
        min_dist[a] = INF;
        a = ancestor[a];
    }
}

void update(int u) {
    int a = u;
    while(a != 0) {
        min_dist[a] = min(min_dist[a], dist[u][level[a]]);
        a = ancestor[a];
    }
}

long long query(int u) {
    int a = u;
    long long res = INF;
    while(a != 0) {
        res = min(res, min_dist[a] + dist[u][level[a]]);
        a = ancestor[a];
    }
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < S; i++) {
        update(X[i] + 1);
    }

    long long ans = INF;
    for(int i = 0; i < T; i++) {
        ans = min(ans, query(Y[i] + 1));
    }

    for(int i = 0; i < S; i++) {
        reset(X[i] + 1);
    }
    return ans;
}

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