제출 #943308

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

factories

#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
const ll INF = 1e18+10;
const int MAXN = 5e5+10;
const int LOG = 21;
 
int n;
vector <pii> adj[MAXN];
ll siz[MAXN], anc[MAXN];
bool rem[MAXN];
 
void subtree(int nw, int par=0){
    siz[nw] = 1;
	for(auto ed : adj[nw]){
        int nx = ed.fi;
		if(nx == par || rem[nx]) continue;
		subtree(nx, nw);
        siz[nw] += siz[nx];
	}
}
ll find(ll nw){
    subtree(nw);
    ll root = nw;
    bool found = 0;
    // if(nw==3){
    //     for(int i=1; i<=n; i++) cout << i << ' ' << siz[i] << " xx\n";
    // }
    //cout<<"in ";
    while(!found){
        found = 1;
        for(auto ed : adj[nw]){ // bisa ke par
            if(rem[ed.fi] || siz[ed.fi] > siz[nw]) continue;
            // ke nx
            if(siz[ed.fi] > siz[root]/2){
                found = 0;
                nw = ed.fi;
                break;
            }
        }
    }
    //cout << root << ' ' << nw << " out\n";
    return nw;
}
 
ll dis[MAXN][LOG+5], dep_cen[MAXN];
void dfs(int nw, int par, ll wei, int dep){
    dis[nw][dep] = wei;
    // cout << nw << " " << wei << endl;
    for(auto nx : adj[nw]){
        if(nx.fi == par || rem[nx.fi]) continue;
        dfs(nx.fi, nw, wei+nx.se, dep);
    }
}
void bd(int nw, int par_cen){
    int cen = find(nw);
    anc[cen] = par_cen;
    dep_cen[cen] = dep_cen[par_cen]+1;
    // cout << cen << ":\n";
    dfs(cen, -1, 0, dep_cen[cen]);
    rem[cen] = 1;
    
    for(auto nx : adj[cen]){
        if(rem[nx.fi]) continue;
        bd(nx.fi, cen);
    }
}
 
ll val[MAXN];
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i=0; i<n-1; i++){
		A[i]++; B[i]++;
        //cout << i << ' ' << A[i] << ' ' << B[i] << " ed\n";
		adj[A[i]].pb(pii(B[i], D[i])); adj[B[i]].pb(pii(A[i], D[i]));
	}
	bd(1, 0);
    //for(int i=1; i<=n; i++) cout << anc[i] << " p\n";
    for(int i=1; i<=n; i++) val[i] = INF;
}
 
void rst(int nw){
    int ANC = nw;
    while(ANC != 0){
        val[ANC] = INF;
        ANC = anc[ANC];
    }
}
void upd(int nw){
    val[nw] = 0;
    int ANC = nw, dep = dep_cen[nw];
    while(ANC != 0){
        ll dist = dis[nw][dep];
        val[ANC] = min(val[ANC], dist);
        ANC = anc[ANC]; dep--;
    }
}
ll que(int nw){
    ll ret = INF;
    int ANC = nw, dep = dep_cen[nw];
    while(ANC != 0){
        ll dist = dis[nw][dep] + val[ANC];
        ret = min(ret, dist);
        ANC = anc[ANC]; dep--;
    }
    return ret;
}
long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0; i<S; i++) upd(X[i]+1);
    //for (int i=1;i<=n;i++) cout<<(val[i]==INF?-1:val[i])<<" ";
    //cout<<endl;
    ll ans = INF;
    for(int i=0; i<T; i++) {
        ans = min(ans, que(Y[i]+1));
        //cout<<que(Y[i]+1)<<' ';
    }
    //cout<<endl;
    for(int i=0; i<S; i++) rst(X[i]+1);
    return ans;
}

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