제출 #926982

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

factories

#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N=5e5+5;
vector <pair <ll,ll> > g[N];
ll jmp[N][20];
ll d[N],dis[N],par[N];
void dfs(int v,int p){
    for(auto to : g[v]){
        if(to.ff!=p){
            d[to.ff]=d[v]+1;
            dis[to.ff]=dis[v]+to.ss;
            par[to.ff]=v;
            jmp[to.ff][0]=v;
            dfs(to.ff,v);
        }
    }
}
ll dist(int u,int v){
    ll ans=dis[u]+dis[v];
    if(d[u]<d[v])swap(u,v);
    int lca=0;
    for(int i=19;i>=0;i--){
        if(d[jmp[u][i]]>=d[v]){
            u=jmp[u][i];
        }
    }
    if(u==v)lca=u;
    else{
        for(int i=19;i>=0;i--){
            if(d[jmp[u][i]]!=d[jmp[v][i]]){
                u=jmp[u][i];
                v=jmp[v][i];
            }
        }
        lca=par[u];
    }
    return ans-dis[lca]*2;
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N-1;i++){
        g[A[i]].pb({B[i],D[i]});
        g[B[i]].pb({A[i],D[i]});
    }
    dfs(0,0);
    for(int i=1;i<20;i++){
        for(int j=0;j<N;j++){
            jmp[j][i]=jmp[jmp[j][i-1]][i-1];
        }
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    ll mn=1e18;
    for(int i=0;i<S;i++){
        for(int j=0;j<T;j++){
            mn=min(mn,dist(X[i],Y[j]));
        }
    }
    return mn;
}
/*signed main(){
    int n,q;
    cin>>n>>q;
    int u[n],v[n],w[n];
    for(int i=0;i<n-1;i++){
        cin>>u[i]>>v[i]>>w[i];
    }
    Init(n,u,v,w);
    while(q--){
        int s,t;
        cin>>s>>t;
        int a[s],b[t];
        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";
    }
}*/

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