Submission #95287

#	Time	Username	Problem	Language	Result	Execution time	Memory
95287		dalgerok	Factories (JOI14_factories)	C++14	100 / 100	7525 ms	182384 KiB

factories

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

const int M = 5e5 + 1, K = 20;
const long long INF = 9e18;


int p[M], d[M];
long long dist[K][M], ans[M];
bool used[M];
vector < pair < int, int > > g[M];

int dfs(int v, int size, int &center, int pr = -1){
    int sz = 1;
    for(auto it : g[v]){
        int to = it.first;
        if(to != pr && !used[to]){
            sz += dfs(to, size, center, v);
        }
    }
    if(center == -1 && sz >= size / 2){
        center = v;
    }
    return sz;
}

void dfs1(int v, int depth, int pr = -1, long long len = 0){
    dist[depth][v] = len;
    for(auto it : g[v]){
        int to = it.first, val = it.second;
        if(to != pr && !used[to]){
            dfs1(to, depth, v, len + val);
        }
    }
}

void build(int v, int pr = -1, int depth = 0){
    int center = -1, tmp = 0;
    dfs(v, dfs(v, 0, tmp), center);
    dfs1(center, depth);
    used[center] = true;
    d[center] = depth;
    p[center] = pr;
    for(auto it : g[center]){
        int to = it.first;
        if(!used[to]){
            build(to, center, depth + 1);
        }
    }
}

void Init(int N, int A[], int B[], int D[]){
    for(int i = 0; i < N - 1; i++){
        g[A[i]].push_back(make_pair(B[i], D[i]));
        g[B[i]].push_back(make_pair(A[i], D[i]));
    }
    for(int i = 0; i < 5e5; i++){
        ans[i] = INF;
    }
    build(0);
}

long long Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++){
        int cur = X[i];
        while(cur != -1){
            ans[cur] = min(ans[cur], dist[d[cur]][X[i]]);
            cur = p[cur];
        }
    }
    long long mn = INF;
    for(int i = 0; i < T; i++){
        int cur = Y[i];
        while(cur != -1){
            mn = min(mn, dist[d[cur]][Y[i]] + ans[cur]);
            cur = p[cur];
        }
    }
    for(int i = 0; i < S; i++){
        int cur = X[i];
        while(cur != -1){
            ans[cur] = INF;
            cur = p[cur];
        }
    }
    return mn;
}

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