제출 #978539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978539		tnknguyen_	공장들 (JOI14_factories)	C++14	0 / 100	8032 ms	149212 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define endl '\n' 
#define ll long long 
#define len(s) (int)s.size() 
#define pii pair<int, int>
//#define int long long 
 
const int MX = 5e5 + 5;
const int LG = 19;
vector<pii> gr[MX];
int up[LG][MX], f[LG][MX], dep[MX];
int n, q;
 
void dfs(int u, int p)  {
    dep[u] = dep[p] + 1, up[0][u] = p;
    for(int j=1; j<LG; ++j){
        up[j][u] = up[j-1][up[j-1][u]];
        f[j][u] = f[j-1][u] + f[j-1][up[j-1][u]];
    }
 
    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(v != p){
            f[0][v] = c;
            dfs(v, u);
        }
    }
}
 
ll dist(int u, int v){
    if(dep[u] < dep[v]) { swap(u, v); }
 
    ll ans = 0;
    for(int j=LG-1; j>=0; --j){
        if(dep[up[j][u]] >= dep[v]){
            ans += f[j][u];
            u = up[j][u];
        }
    }
 
    if(u == v) { return ans; }
 
    for(int j=LG-1; j>=0; --j){
        if(up[j][u] != up[j][v]){
            ans += f[j][u] + f[j][v];
            u = up[j][u], v = up[j][v];
        }
    }
    return ans + f[0][u] + f[0][v];
}
 
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i=0; i<n; ++i){
        int u = A[i], v = B[i], c = D[i];
        ++u, ++v;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
    }
 
    dfs(1, 1);
}
 
ll Query(int S, int X[], int T, int Y[]){
    ll ans = 1e18;
    for(int i=0; i<S; ++i){
        for(int j=0; j<T; ++j){
            ans = min(ans, dist(X[i]+1, Y[j]+1));
        }
    }
    return ans;
}

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