제출 #839516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839516		imarn	공장들 (JOI14_factories)	C++14	100 / 100	4408 ms	353452 KiB

factories

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N=5e5+5;
vector<pair<int,ll>>g[N];
int sz[N]{0};
bool vis[N]{0};
ll dp[N]{0};
vector<pair<int,ll>>ancestor[N];
int getsize(int u,int p){
    sz[u]=1;
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        sz[u]+=getsize(v.f,u);
    }return sz[u];
}
int get_centroid(int u,int p,int n){
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        if(sz[v.f]*2>n)return get_centroid(v.f,u,n);
    }return u;
}
void gen_dist(int u,int p,int centroid,ll cur){
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        gen_dist(v.f,u,centroid,cur+v.s);
    }ancestor[u].pb({centroid,cur});
}
void play(int u=0){
    int centroid=get_centroid(u,u,getsize(u,u));
    for(auto v:g[centroid]){
        if(vis[v.f])continue;
        gen_dist(v.f,centroid,centroid,v.s);
    }vis[centroid]=1;
    for(auto v:g[centroid]){
        if(vis[v.f])continue;
        play(v.f);
    }
}
void upd(int u){
    for(auto v:ancestor[u]){
        dp[v.f]=min(dp[v.f],v.s);
    }dp[u]=0;
}
ll qry(int u){
    ll ans=dp[u];
    for(auto v:ancestor[u]){
        ans=min(ans,v.s+dp[v.f]);
    }return ans;
}
void Init(int N,int A[],int B[],int D[]){
    for(int i=0;i<N;i++)dp[i]=1e16;
    for(int i=0;i<N-1;i++){
        g[A[i]].pb({B[i],D[i]});g[B[i]].pb({A[i],D[i]});
    }play();
}
long long Query(int S,int X[],int T,int Y[]){
    for(int i=0;i<S;i++){
        upd(X[i]);
    }
    ll ans=1e16;
    for(int i=0;i<T;i++){
        ans=min(ans,qry(Y[i]));
    }
    for(int i=0;i<S;i++){
        dp[X[i]]=1e16;
        for(auto it : ancestor[X[i]])dp[it.f]=1e16;
    }
    return ans;
}

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