Submission #735625

#	Time	Username	Problem	Language	Result	Execution time	Memory
735625		Jeff12345121	공장들 (JOI14_factories)	C++14	0 / 100	8022 ms	123784 KiB

factories

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

typedef long long ll;
vector<vector<pair<int,int>>> g;
int n;
const int nmax = 500005,LOG = 20;
int lift[LOG][nmax],dis[LOG][nmax],depth[nmax];
void find_parents(int node) {
    for (auto k : g[node]) {
        if (k.first == lift[0][node]) {
            continue;
        }

        lift[0][k.first] = node;
        dis[0][k.first] = k.second;
        depth[k.first] = depth[node] + 1;
        find_parents(k.first);
    }
}
void get_lift() {
    find_parents(1);

    for (int lvl = 1; lvl < LOG; lvl++) {
        for (int i = 1; i <= n; i++) {
            lift[lvl][i] = lift[lvl - 1][lift[lvl - 1][i]];
            dis[lvl][i] = dis[lvl-1][lift[lvl-1][i]] + dis[lvl-1][i];
        }
    }
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    g.resize(n + 1);
    for (int i = 1; i < n; i++) {
        A[i - 1]++;
        B[i - 1]++;
        g[A[i - 1]].push_back({B[i - 1] , D[i - 1]});
        g[B[i - 1]].push_back({A[i - 1], D[i - 1]});
    }

    get_lift();

    return;
}

const ll inf = (1LL << 60);

ll get_dis(int u, int v) {
    if (u == v) {
        return 0;
    }

    if (depth[u] < depth[v]) {
        swap(u,v);
    }

    int cost = 0;
    for (int lvl = LOG - 1; lvl >= 0 && depth[u] > depth[v]; lvl--) {
        if (depth[lift[lvl][u]] >= depth[v]) {
            cost += dis[lvl][u];
            u = lift[lvl][u];
        }
    }

    if (u == v) {
        return cost;
    }

    for (int lvl = LOG - 1; lvl >= 0; lvl--) {
        if (lift[lvl][u] != lift[lvl][v]) {
            cost += dis[lvl][u];
            u = lift[lvl][u];
            cost += dis[lvl][v];
            v = lift[lvl][v];
        }
    }

    cost += dis[0][u];
    cost += dis[0][v];
    return cost;
}
long long Query(int S, int X[], int T, int Y[]) {
    ll sol = inf;
    for (int i = 0; i < S;i++) {
        X[i]++;
    }
    for (int i = 0; i < T;i++){
        Y[i]++;
    }

    for (int i = 1; i <= S; i++) {
        for (int j = 1; j <= T; j++) {
            sol = min(sol , get_dis(X[i - 1] , Y[j - 1]));
        }
    }
    return sol;
}

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