Submission #883322

#	Time	Username	Problem	Language	Result	Execution time	Memory
883322		vjudge1	Factories (JOI14_factories)	C++17	0 / 100	8055 ms	524288 KiB

factories

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

typedef long long ll;
const ll INF = 1'000'000'000'000'000'000;

const int N = 500'000;
const int M = 20;

int n, q, sz[N + 10];
bool mark[N + 10];
ll mn[N + 10];
vector<pair<int, ll>> adj[N + 10];
vector<pair<int, ll>> up[N + 10];

int calcSz(int u, int par = 0) {
    sz[u] = 1;
    for (auto [v, w]: adj[u])
        if (!mark[v] && v != par)
            sz[u] += sz[v];
    return sz[u];
}

int calcCentroid(int u) {
    calcSz(u);
    int res = u;
    while (true) {
        bool ok = true;
        for (auto [v, w]: adj[res])
            if (!mark[v] && sz[v] < sz[res] && sz[v] > sz[u] / 2) {
                res = v;
                ok = false;
                break;
            }
        if (ok)
            return res;
    }
}

void calcH(int u, int root, int par = 0, ll h = 0) {
    up[u].push_back({root, h});
    for (auto [v, w]: adj[u])
        if (!mark[v] && v != par)
            calcH(v, root, u, h + w);
}

void makeGraph(int u = 1) {
    u = calcCentroid(u);
    calcH(u, u);
    mark[u] = true;
    for (auto [v, w]: adj[u])
        if (!mark[v])
            makeGraph(v);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; i++) {
        A[i]++;
        B[i]++;
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    makeGraph();
    fill(mn + 1, mn + n + 1, INF);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        X[i]++;
        for (auto [u, w]: up[X[i]])
            mn[u] = min(mn[u], w);
    }
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        Y[i]++;
        for (auto [u, w]: up[Y[i]])
            ans = min(ans, mn[u] + w);
    }
    for (int i = 0; i < S; i++)
        for (auto [u, w]: up[X[i]])
            mn[u] = INF;
    return ans;
}

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