Submission #883351

#	Time	Username	Problem	Language	Result	Execution time	Memory
883351		vjudge1	Factories (JOI14_factories)	C++17	100 / 100	2692 ms	287728 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], cnt[N + 10];
bool mark[N + 10];
ll mn[N + 10];
vector<pair<int, ll>> adj[N + 10];
pair<int, ll> up[N + 2][M + 2];
//int A[N + 10], B[N + 10], D[N + 10], X[N + 10], Y[N + 10], S, T;

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

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

void calcH(int u, int root, int par = 0, ll h = 0) {
    up[u][cnt[u]++] = {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 (int t = 0; t < cnt[X[i]]; t++)
            mn[up[X[i]][t].first] = min(mn[up[X[i]][t].first], up[X[i]][t].second);
    }
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        Y[i]++;
        for (int t = 0; t < cnt[Y[i]]; t++)
            ans = min(ans, mn[up[Y[i]][t].first] + up[Y[i]][t].second);
    }
    for (int i = 0; i < S; i++) 
        for (int t = 0; t < cnt[X[i]]; t++)
            mn[up[X[i]][t].first] = INF;
    return ans;
}

/*int main() {
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++)
        cin >> A[i] >> B[i] >> D[i];
    Init(n);
    vector<ll> vec;
    while (q--) {
        cin >> S >> T;
        for (int i = 0; i < S; i++)
            cin >> X[i];
        for (int i = 0; i < T; i++)
            cin >> Y[i];
        vec.push_back(Query());
    }
    for (auto x: vec)
        cout << x << ' ';
    cout.flush();
    return 0;
}*/

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