Submission #993795

#	Time	Username	Problem	Language	Result	Execution time	Memory
993795		Albertstein	Factories (JOI14_factories)	C++17	15 / 100	8031 ms	115792 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define pii pair<int, int>
using namespace std;

const long long maxn = 500001, mbit = 20, INF = LLONG_MAX / 3;
int n;
bool rem[maxn];
int sub_sz[maxn];
int stp[maxn][mbit];
int dth[maxn];
long long dst[maxn];
int cen[maxn];
long long mini[maxn];
vector <pii > G [maxn];

int dfs(int u, int p = -1){
    sub_sz[u] = 1;
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            sub_sz[u] += dfs(v, u);
        }
    }
    return sub_sz[u];
}

int g_cen(int u, int sz, int p = -1){
    for(auto [v, d] : G[u]){
        if(v != p && !rem[v]){
            if(sub_sz[v] * 2 > sz){
                return g_cen(v, sz, u);
            }
        }
    }
    return u;
}

int sol(int r = 0){
    int c = g_cen(r, dfs(r));
    rem[c] = 1;
    for(auto [v, d] : G[c]){
        if(!rem[v]){
            cen[sol(v)] = c;
        }
    }
    return c;
}

void LCA_dfs(int u){
    for(int i = 1; i < mbit; i++){
        stp[u][i] = stp[stp[u][i - 1]][i - 1];
    }
    for(auto [v, d] : G[u]){
        if(v != stp[u][0]){
            stp[v][0] = u;
            dth[v] = dth[u] + 1;
            dst[v] = dst[u] + d;
            LCA_dfs(v);
        }
    }
}

int LCA(int u, int v){
    if(dth[u] < dth[v]) swap(u, v);
    for(int i = mbit - 1; i >= 0; i--){
        if(dth[u] - dth[v] >= (1<<i)){
            u = stp[u][i];
        }
    }
    if(u == v) return u;
    for(int i = mbit - 1; i >= 0; i--){
        if(stp[u][i] != stp[v][i]){
            u = stp[u][i];
            v = stp[v][i];
        }
    }
    return stp[u][0];
}

long long Dist(int u, int v){
    int c = LCA(u, v);
    return dst[u] + dst[v] - 2 * dst[c];
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0; i < N - 1; i++){
        int a = A[i], b = B[i], d = D[i];
        G[a].push_back({b, d});
        G[b].push_back({a, d});
    }
    cen[sol()] = -1;
    LCA_dfs(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    long long ans = INF;
    fill(mini, mini + maxn, INF);
    for(int i = 0; i < S; i++){
        int x = X[i];
        int v = x;
        while(v != -1){
            mini[v] = min(mini[v], Dist(x, v));
            v = cen[v];
        }
    }
    for(int i = 0; i < T; i++){
        int y = Y[i];
        int v = y;
        while(v != -1){
            ans = min(ans, mini[v] + Dist(y, v));
            v = cen[v];
        }
    }//*/
    return ans;
}

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