제출 #222909

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

factories

#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=1987654321987654321;
int n, q, siz[500010], d[500010], sparse[500010][30], centpar[500010];
vector<pil> link[500010];
bool ch[500010];
LL dep[500010];
void dfs(int num, int par){
    siz[num]=1;
    d[num]=d[par]+1;
    sparse[num][0]=par;
    for(auto i:link[num]){
        if(i.F==par)continue;
        dep[i.F]=dep[num]+i.S;
        dfs(i.F, num);
        siz[num]+=siz[i.F];
    }
}
int lca(int x, int y){
    if(d[x]>d[y])swap(x, y);
    for(int i=20; i>=0; i--){
        if(d[y]-d[x]>=(1<<i))y=sparse[y][i];
    }
    if(x==y)return x;
    for(int i=20; i>=0; i--){
        if(sparse[x][i]!=sparse[y][i]){
            x=sparse[x][i];
            y=sparse[y][i];
        }
    }
    return sparse[x][0];
}
inline LL dist(int x, int y){return dep[x]+dep[y]-2*dep[lca(x, y)];}
int get_centroid(int num, int par, int sz){
    bool flag=true;
    for(auto i:link[num]){
        if(ch[i.F])continue;
        if(siz[i.F]>sz/2)flag=false;
    }
    if(flag)return num;
    for(auto i:link[num]){
        if(i.F==par||ch[i.F])continue;
        int temp=siz[i.F];
        siz[num]=sz-siz[i.F];
        siz[i.F]=sz;
        int ret=get_centroid(i.F, num, sz);
        if(ret)return ret;
        siz[num]=sz;
        siz[i.F]=temp;
    }
    return 0;
}
void make_centroidtree(int num, int par){
    int cen=get_centroid(num, 0, siz[num]);
    ch[cen]=true;
    centpar[cen]=par;
    for(auto i:link[cen]){
        if(ch[i.F])continue;
        make_centroidtree(i.F, cen);
    }
}
pil arr[500010];
vector<pil> up[500010];
void Init(int N, int A[], int B[], int D[]){
    n=N;
    for(int i=0; i<n-1; i++){
        int a=A[i];
        int b=B[i];
        LL c=(LL)D[i];
        link[a+1].pb(mp(b+1, c));
        link[b+1].pb(mp(a+1, c));
    }
    dfs(1, 0);
    for(int j=1; j<=20; j++){
        for(int i=1; i<=n; i++){
            sparse[i][j]=sparse[sparse[i][j-1]][j-1];
        }
    }
    make_centroidtree(1, 0);
    for(int i=1; i<=n; i++){
        int now=i;
        while(now){
            up[i].pb(mp(now, dist(i, now)));
            now=centpar[now];
        }
    }
}
int qq=0;
LL Query(int S, int X[], int T, int Y[]){
    qq--;
    for(int i=0; i<S; i++){
        for(auto j:up[X[i]+1])arr[j.F]=min(arr[j.F], mp(qq, j.S));
    }
    LL ret=llinf;
    for(int i=0; i<T; i++){
        for(auto j:up[Y[i]+1]){
            if(arr[j.F].F==qq)ret=min(ret, arr[j.F].S+j.S);
        }
    }
    return ret;
}

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