제출 #959610

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

factories

#include <bits/extc++.h>
#include "factories.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll n, q;
ll sz[500050], use[500050], cent_papa[500050], dep[500050], papa_dist[500050];
ll dp[500050];
vector<pll> adj[500050];
ll m[500050];

ll get_size(ll u, ll p=0) {
    sz[u]=1;
    for(auto& [v, w]:adj[u]) {
        if(use[v] || p==v) continue;
        sz[u]+=get_size(v,u);
    }
    return sz[u];
}

pll get_cent(ll u, ll p, ll cnt, ll d) {
    for(auto& [v, w]:adj[u]) {
        if(use[v] || v==p) continue;
        if(sz[v]>cnt/2) return get_cent(v,u,cnt,d+w);
    }
    return {u, d};
}

void dnc(ll u, ll p=0, ll x=0) {//p는 이전 cent
    auto [cent, dist]=get_cent(u,p,get_size(u,p),x);
    //cout<<cent<<' '<<dist<<endl;
    cent_papa[cent]=p;
    papa_dist[cent]=dist;
    use[cent]=1;
    for(auto& [v, w]:adj[cent]) if(!use[v]) dnc(v,cent,w);
}

void update(ll u) {
    ll now=u;
    ll nowdist=0;
    do {
        m[now]=min(m[now],nowdist);
        nowdist+=papa_dist[now];
        now=cent_papa[now];
    } while(now);    
}

void downdate(ll u) {
    ll now=u;
    do {
        m[now]=1e18;
        now=cent_papa[now];
    } while(now);    
}

ll query(ll u) {
    ll now=u;
    ll ret=1e18, D=0;
    do {        
        ret=min(ret, D + m[now]);
        D+=papa_dist[now];
        now=cent_papa[now];        
    } while(now);
    return (ret<1e18) ? ret : -1;
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0;i<n-1;i++) {
        adj[A[i]+1].emplace_back(B[i]+1,D[i]);
        adj[B[i]+1].emplace_back(A[i]+1,D[i]);
    }
    dnc(1);
    fill(m+1,m+n+1,1e18);
}
 
long long Query(int S, int X[], int T, int Y[]) {
    ll ret=1e18;
    for(int i=0;i<S;i++) update(X[i]+1);
    for(int i=0;i<T;i++) ret=min(ret,query(Y[i]+1));
    for(int i=0;i<S;i++) downdate(X[i]+1);
    return ret;
}

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