제출 #1084967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084967		pemguimn	공장들 (JOI14_factories)	C++14	15 / 100	4017 ms	226896 KiB

factories

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

const int maxN = 5e5 + 5, LOG = 20;
const long long INF = (long long) 1e18 + 5;
vector<pair<int, int>> adj[maxN];

int h[maxN], par[LOG][maxN];

const int SMALL = 5e3 + 5;
long long d[SMALL][SMALL];
long long w[maxN];
void dfs(int i, int pre){
    for(pair<int, int> e : adj[i]){
        int x = e.first, c = e.second;
        if(x == pre) continue;
        h[x] = h[i] + 1, w[x] = w[i] + c;
        par[0][x] = i;
        for(int j = 1; j < LOG; j++) par[j][x] = par[j - 1][par[j - 1][x]];
        dfs(x, i);
    }
}

int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    for(int i = 0; i < LOG; i++){
        if(d & (1 << i)) x = par[i][x];
    }
    if(x == y) return x;
    for(int i = LOG - 1; i >= 0; i--){
        if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
    }
    return par[0][x];
}

map<pair<int, int>, long long> mp;

void Init(int N, int A[], int B[], int D[]){
    for(int i = 0; i < N - 1; i++){
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
    if(N < SMALL){
        for(int i = 0; i < min(N, SMALL); i++){
            for(int j = 0; j < min(N, SMALL); j++){
                d[i][j] = w[i] + w[j] - 2 * w[lca(i, j)];
            }
        }
    }
}

const int B = 700;
long long Query(int S, int X[], int T, int Y[]){
    sort(X, X + S), sort(Y, Y + T);
    long long ans = INF;
    if(max(X[S - 1], Y[T - 1]) < SMALL){
        for(int i = 0; i < S; i++){
            for(int j = 0; j < T; j++){
                ans = min(ans, d[X[i]][Y[j]]);
            }
        }

    } else{
        for(int i = 0; i < S; i++){
            for(int j = 0; j < T; j++){
                ans = min(ans, w[X[i]] + w[Y[j]] - 2 * w[lca(X[i], Y[j])]);
            }
        }
    }
    return ans;
}

#ifdef LOCAL
const int MAX = 1e3 + 5;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n, q; cin >> n >> q;
    int x[MAX], y[MAX], d[MAX];
    for(int i = 0; i < n - 1; i++){
        cin >> x[i] >> y[i] >> d[i];
    }
    Init(n, x, y, d);
    for(int i = 1; i <= q; i++){
        int s, t; cin >> s >> t;
        int a[MAX], b[MAX];
        for(int i = 0; i < s; i++) cin >> a[i];
        for(int i = 0; i < t; i++) cin >> b[i];
        cout << Query(s, a, t, b) << '\n';
    }
    return 0;
}
#endif

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