Submission #894631

#	Time	Username	Problem	Language	Result	Execution time	Memory
894631		IWKR	Factories (JOI14_factories)	C++17	100 / 100	3135 ms	231208 KiB

factories

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

vector<pair<int, int>> adjlist[500001];
int subsz[500001], level[500001], centpar[500001][20];
long long dist[500001][20], ans[500001];
vector<int> v;

void dfs(int x, int p) {
    subsz[x] = 1;
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        dfs(i.first, x);
        subsz[x] += subsz[i.first];
    }
}

int centroid(int x, int p, int treesz) {
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        if (treesz < subsz[i.first] * 2) {
            return centroid(i.first, x, treesz);
        }
    }
    return x;
}

void dfs2(int x, int p, int l, int cent, long long cost) {
    centpar[x][l] = cent;
    dist[x][l] = cost;
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        dfs2(i.first, x, l, cent, cost + i.second);
    }
}

void decomp(int x, int p, int l) {
    dfs(x, -1);
    int cent = centroid(x, -1, subsz[x]);
    level[cent] = l;
    dfs2(cent, -1, l, cent, 0);
    for (auto i: adjlist[cent]) {
        if (level[i.first] == 0) {
            decomp(i.first, cent, l + 1);
        }
    }
}

void update(int x) {
    for (int i = 1; i <= level[x]; i++) {
        ans[centpar[x][i]] = min(ans[centpar[x][i]], dist[x][i]);
        v.push_back(centpar[x][i]);
    }
}

long long query(int x) {
    long long ans2 = LLONG_MAX;
    for (int i = 1; i <= level[x]; i++) {
        if (ans[centpar[x][i]] == LLONG_MAX) {
            continue;
        }
        ans2 = min(ans2, ans[centpar[x][i]] + dist[x][i]);
    }
    return ans2;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        adjlist[A[i]].push_back({B[i], D[i]});
        adjlist[B[i]].push_back({A[i], D[i]});
    }
    decomp(0, -1, 1);
    for (int i = 0; i < N; i++) {
        ans[i] = LLONG_MAX;
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        update(X[i]);
    }
    long long ans2 = LLONG_MAX;
    for (int i = 0; i < T; i++) {
        ans2 = min(ans2, query(Y[i]));
    }
    for (auto i: v) {
        ans[i] = LLONG_MAX;
    }
    v.clear();
    return ans2;
}

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