Submission #926980

#	Time	Username	Problem	Language	Result	Execution time	Memory
926980		Aiperiii	Factories (JOI14_factories)	C++14	0 / 100	179 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;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;
}

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