제출 #708434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708434		Dan4Life	공장들 (JOI14_factories)	C++17	0 / 100	3902 ms	152264 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
using ll = long long;
const int mxN = (int)5e5+10;
const int mxLg = (int)22;
const ll LINF = (ll)4e18;
int n, sub[mxN], par[mxN], vis[mxN], lev[mxN];
ll best[mxN], dis[mxN][mxLg];
vector<pair<int,ll>> adj[mxN];

int fcentroid(int s, int p, int n){
    for(auto x : adj[s]){
        int u = x.fi;
        if(u!=p and sub[u]>n/2 and !vis[u])
            return fcentroid(u,s,n);
    }
    return s;
}

int dfs(int s, int p, int S, bool ok){
    sub[s]=1;
    for(auto x : adj[s]){
        int u = x.fi, w = x.se; if(u==p) continue;
        if(ok) dis[u][lev[u]-lev[S]]=dis[s][lev[s]-lev[S]]+w;
        if(!vis[u]) sub[s]+=dfs(u,s, S,ok);
    }
    return sub[s];
}

void centroid_decomp1(int s, int p, int l){
    int n = dfs(s,p,s,0);
    int centroid = fcentroid(s,p,n);
    vis[centroid] = 1; par[centroid] = p; lev[centroid]=l;
    for(auto x : adj[centroid]){
        int u = x.fi;
        if(u!=p and !vis[u])
            centroid_decomp1(u,centroid,l+1);
    }
}

void centroid_decomp(int s, int p){
    int n = dfs(s,p,s,0);
    int centroid = fcentroid(s,p,n);
    vis[centroid] = 1; par[centroid] = p;
    dfs(centroid,p,centroid,1);
    for(auto x : adj[centroid]){
        int u = x.fi;
        if(u!=p and !vis[u])
            centroid_decomp(u,centroid);
    }
}

void Init(int N, int a[], int b[], int d[]) {
    n = N; memset(par,-1,sizeof(par));
    memset(best,-1,sizeof(best));
    for(int i = 0; i < n-1; i++){
        adj[a[i]].pb({b[i],d[i]});
        adj[b[i]].pb({a[i],d[i]});
    }
    centroid_decomp1(0,-1,0);
    fill(vis,vis+n,0);
    centroid_decomp(0,-1);
}

ll Query(int s, int x[], int t, int y[]) {
    for(int i = 0; i < s; i++){
        int a = x[i], j = 0;
        while(a!=-1){
            ll DD = dis[x[i]][j];
            if(best[a]==-1) best[a]=DD;
            else best[a]=min(best[a],DD);
            a = par[a], j++;
        }
    }
    ll ans = LINF;
    for(int i = 0; i < t; i++){
        int x = y[i], j = 0;
        while(x!=-1){
            if(best[x]!=-1) ans = min(ans, dis[y[i]][j]+best[x]);
            x=par[x], j++;
        }
    }
    for(int i = 0; i < s; i++){
        int a = x[i];
        while(a!=-1) best[a]=-1, a = par[a];
    }
    return ans;
}

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