Submission #43717

#	Time	Username	Problem	Language	Result	Execution time	Memory
43717		aaron248	공장들 (JOI14_factories)	C++14	15 / 100	6096 ms	291564 KiB

factories

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

#define ll long long
#define pii pair<int,ll>
#define X first
#define Y second
const int maxn = 5e5 + 5;
const int mlog = 19;
const ll inf = 1e16;

int n;
vector<pii> way[maxn];
int h[maxn], par[maxn][21];
ll dist[maxn][21];
int sz[maxn], used[maxn];
int cpar[maxn];
ll far[maxn];

void dfs(int u, int last, ll lval) {
    h[u] = h[last] + 1;
    par[u][0] = last; dist[u][0] = lval;
    for(int i=1;i<=mlog;i++) {
        par[u][i] = par[par[u][i-1]][i-1];
        dist[u][i] = dist[u][i-1] + dist[par[u][i-1]][i-1];
    }
    for(auto t : way[u]) {
        int v = t.X; ll val = t.Y;
        if(v==last) continue;
        dfs(v, u, val);
    }
}

ll lca(int u, int v) {
    ll res = 0;
    if(h[u]<h[v]) swap(u, v);
    for(int i=mlog;i>=0;i--) {
        if(h[par[u][i]]>=h[v]) {
            res += dist[u][i];
            u = par[u][i];
        }
    }
    if(u==v) return res;
    for(int i=mlog;i>=0;i--) {
        if(par[u][i]!=par[v][i]) {
            res += dist[u][i] + dist[v][i];
            u = par[u][i]; v = par[v][i];
        }
    }
    return res + dist[u][0] + dist[v][0];
}

void survey(int u, int last) {
    sz[u] = 1;
    for(auto t : way[u]) {
        int v = t.X;
        if(v==last || used[v]) continue;
        survey(v, u);
        sz[u] += sz[v];
    }
}

int decom(int u) {
    survey(u,0);
    int x = u, last = 0;
    redo:
    for(auto t : way[x]) {
        int y = t.X;
        if(y==last || used[y]) continue;
        if(sz[y]>sz[u]/2) {
            last = x; x = y;
            goto redo;
        }
    }
    used[x] = 1;
    for(auto t : way[x]) {
        int y = t.X;
        if(used[y]) continue;
        int temp = decom(y);
        cpar[temp] = x;
    }
    return x;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0;i<n-1;i++) {
        int x = A[i]+1, y = B[i]+1;
        ll val = D[i];
        way[x].push_back({y,val});
        way[y].push_back({x,val});
    }
    dfs(1,0,0);
    decom(1);
    for(int i=1;i<=n;i++) far[i] = inf;
}

ll Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<T;i++) {
        int u = Y[i]+1, x = u;
        while(x) {
            far[x] = min(far[x], lca(x, u));
            x = cpar[x];
        }
    }
    ll res = inf;
    for(int i=0;i<S;i++) {
        int u = X[i]+1, x = u;
        while(x) {
            res = min(res, far[x] + lca(x,u));
            x = cpar[x];
        }
    }
    for(int i=0;i<T;i++) {
        int u = Y[i]+1, x = u;
        while(x) {
            far[x] = inf;
            x = cpar[x];
        }
    }
    return res;
}

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