제출 #1276894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276894		trandangquang	Factories (JOI14_factories)	C++20	100 / 100	5090 ms	125844 KiB

factories

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

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int NX=5e5+5;
const int LG=18;

int n;
int sz[NX],pcen[NX]; bool del[NX];
int up[NX][LG+1],h[NX]; ll d[NX];
ll minD[NX];
vector<ii> adj[NX];

void get_sz(int u, int p=-1){
    sz[u]=1;
    for(auto [v,w]:adj[u]) if(v!=p && !del[v]){
        get_sz(v,u);
        sz[u]+=sz[v];
    }
}
int get_cen(int u, int szA, int p=-1){
    for(auto [v,w]:adj[u]) if(v!=p && !del[v]){
        if(sz[v]>szA/2) return get_cen(v,szA,u);
    }
    return u;
}
void decomp(int u, int lst=-1){
    get_sz(u);
    int cen=get_cen(u,sz[u]);

    pcen[cen]=lst;
    del[cen]=1;
    for(auto [v,w]:adj[cen]) if(!del[v]) decomp(v,cen);
}
void dfs(int u, int p=-1){
    for(auto [v,w]:adj[u]) if(v!=p){
        h[v]=h[u]+1;
        up[v][0]=u;
        foru(i,1,LG) up[v][i]=up[up[v][i-1]][i-1];
        d[v]=d[u]+w;
        dfs(v,u);
    }
}
int lca(int u, int v){
    if(h[u]<h[v]) swap(u,v);
    int d=h[u]-h[v];
    foru(i,0,LG) if(bit(d,i)) u=up[u][i];
    if(u==v) return u;

    ford(i,LG,0){
        if(up[u][i]!=up[v][i]){
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}
ll dist(int u, int v){
    return d[u]+d[v]-2*d[lca(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
    n=N;
    rep(i,n-1){
        adj[A[i]].eb(B[i],D[i]);
        adj[B[i]].eb(A[i],D[i]);
    }

    decomp(0);
    dfs(0);
    memset(minD,0x3f,sizeof(minD));
}

ll Query(int S, int X[], int T, int Y[]) {
    rep(i,S){
        int t=X[i];
        while(t!=-1){
            mini(minD[t], dist(X[i],t));
            t=pcen[t];
        }
    }
//
    ll res=1e18;
    rep(i,T){
        int t=Y[i];
        while(t!=-1){
            mini(res, minD[t]+dist(Y[i],t));
//            cerr<<minD[t] _ dist(Y[i],t)<<'\n';
            t=pcen[t];
        }
    }

    rep(i,S){
        int t=X[i];
        while(t!=-1){
            minD[t]=1e18;
            t=pcen[t];
        }
    }

    return res;
//    return 0;
}

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