제출 #549602

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

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MAXN = 500000, LOGN = 21;
vector<vector<pair<int,int>>> adj(MAXN);
int depth[MAXN],par[MAXN][LOGN];
long long int dis[MAXN],dist[5000][5000];
int lca(int u, int v){
    if (depth[u] < depth[v]){
        swap(u,v);
    }
    int k = depth[u]-depth[v];
    for (int j = LOGN-1; j >= 0; j--){
        if (k & (1<<j)){
            u = par[u][j];
        }
    }
    if (u == v){
        return v;
    }
    for (int j = LOGN-1; j >= 0; j--){
        if (par[u][j] != par[v][j]){
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}
long long int Query(int S, int X[], int T, int Y[]){
    long long int ans = 1e18;
    for (int i = 0; i < S; i++){
        for (int j = 0; j < T; j++){
            //int l = lca(X[i],Y[j]);
            ans = min(ans,dist[X[i]][Y[j]]);
          //  cout << X[i] << " " << Y[j] << " " << dis[X[i]] << " " << dis[Y[j]] << " " << 2*dis[l] << "\n";
        }
    }
    return ans;
}
void dfs(int x, int p = 0, int d = 0,long long int w = 0LL){
    depth[x] = d;
    dis[x] = dis[p]+w;
    par[x][0] = p;
    for (int i = 1; i < LOGN; i++){
        par[x][i] = par[par[x][i-1]][i-1];
       // dis[x][i] = dis[x][i-1]+dis[par[x][i-1]][i-1];
    }
    for (auto ch: adj[x]){
        if (ch.first!=p){
            dfs(ch.first,x,d+1,ch.second);
        }
    }
}
void Init(int N, int A[], int B[], int D[]){
    int n  = N;
    for (int i = 0; i < n-1; i++){
        adj[A[i]].push_back({B[i],(long long int)D[i]});
        adj[B[i]].push_back({A[i],(long long int)D[i]});
    }
    dfs(0);
    for (int i = 0; i < n; i++){
        for (int j = i; j < n; j++){
            dist[i][j] = dis[i]+dis[j]-(2*dis[lca(i,j)]);
            dist[j][i] = dist[i][j];
        }
    }
}

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