Submission #993782

#	Time	Username	Problem	Language	Result	Execution time	Memory
993782		Albertstein	Factories (JOI14_factories)	C++17	0 / 100	1793 ms	524288 KiB

factories

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

const int maxn = 500001, mbit = 20, INF = 100000;
int n;
bool rem[maxn];
int sub_sz[maxn];
int stp[maxn][mbit];
int dth[maxn];
int dst[maxn];
int cen[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;
}

int 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];
}

int 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[]) {
    int ans = INF;
    vector <int> 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;
}

Compilation message (stderr)

factories.cpp: In function 'int LCA_dfs(int)':
factories.cpp:60:1: warning: no return statement in function returning non-void [-Wreturn-type]
   60 | }
      | ^

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