제출 #62119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62119		Osama_Alkhodairy	공장들 (JOI14_factories)	C++17	0 / 100	8061 ms	123608 KiB

factories

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

int n, dep[500001], par[500001][20];
ll sum[500001];
vector <pair <int, ll> > v[500001];

void dfs(int node, int pnode, int d, ll s){
    par[node][0] = pnode;
    dep[node] = d;
    sum[node] = s;
    for(auto &i : v[node])
        if(i.first != pnode)
            dfs(i.first, node, d + 1, s + i.second);
}
void build(){
    dfs(0, -1, 0, 0);
    int cur = 1;
    while((1 << cur) <= n){
        for(int i = 0 ; i < n ; i++){
            if(par[i][cur - 1] == -1) par[i][cur] = -1;
            else par[i][cur] = par[par[i][cur - 1]][cur - 1];
        }
        cur++;
    }
}
int lift(int node, int dist){
    for(int i = 19 ; i >= 0 ; i--)
        if((1 << i) & dist)
            node = par[node][i];
    return node;
}
int LCA(int a, int b){
    if(dep[a] > dep[b])
        swap(a, b);
    b = lift(b, dep[b] - dep[a]);
    if(a == b) return a;
    for(int i = 19 ; i >= 0 ; i--){
        if(par[a][i] != par[b][i]){
            a = par[a][i];
            b = par[b][i];
        }
    }
    return par[a][0];
}
ll dist(int a, int b){
    int lca = LCA(a, b);
    return sum[a] + sum[b] - 2 * sum[lca];
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0 ; i < N - 1 ; i++){
        v[A[i]].push_back(make_pair(B[i], D[i]));
        v[B[i]].push_back(make_pair(A[i], D[i]));
    }
    build();
}
long long Query(int S, int X[], int T, int Y[]) {
    ll ret = 1e18;
    for(int i = 0 ; i < S ; i++)
        for(int j = 0 ; j < T ; j++)
            ret = min(ret, dist(X[i], Y[j]));
    return ret;
}

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