Submission #767769

#	Time	Username	Problem	Language	Result	Execution time	Memory
767769		Abrar_Al_Samit	Factories (JOI14_factories)	C++17	100 / 100	7534 ms	224060 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const int nax = 5e5 + 3;
const int lg = 20;

vector<pair<int, int>>g[nax];
int CT_par[nax];

int st[nax], en[nax], tt = 0;
int up[nax][lg];
long long d[nax];
int sub[nax];

void dfs(int v, int p) {
    st[v] = tt++;
    up[v][0] = p;

    for(int j=1; j<lg; ++j) {
        up[v][j] = up[up[v][j-1]][j-1];
    }

    for(auto [u, w] : g[v]) if(u!=p) {
        d[u] = d[v] + w;
        dfs(u, v);
    }
    en[v] = tt-1;
}

bool ban[nax];

int cdfs(int v, int p = -1) {
    sub[v] = 1;
    for(auto [u, w] : g[v]) if(u!=p && !ban[u]) {
        sub[v] += cdfs(u, v);
    }
    return sub[v];
}
int get_centroid(int v, int sz, int p = -1) {
    for(auto [u, w] : g[v]) if(sub[u]*2>sz && u!=p && !ban[u]) {
        return get_centroid(u, sz, v);
    }
    return v;
}
void centroid(int v, int prevCen = -1) {
    int C = get_centroid(v, cdfs(v));

    CT_par[C] = prevCen;

    ban[C] = 1;
    for(auto [u, w] : g[C]) if(!ban[u]) {
        centroid(u, C);
    }
}

bool is_anc(int u, int v) {
    return st[u]<=st[v] && en[u]>=en[v];
}
int getLCA(int u, int v) {
    for(int j=lg-1; j>=0; --j) if(!is_anc(up[u][j], v)) {
        u = up[u][j];
    }
    if(!is_anc(u, v)) u = up[u][0];
    return u;
}
long long get_dist(int u, int v) {
    int lca = getLCA(u, v);
    return d[u] + d[v] - 2 * d[lca];
}
long long ans[nax];
long long mem[nax][lg];
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i<N; ++i) {
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }

    dfs(0, 0);
    centroid(0);

    for(int i=0; i<N; ++i) {
        ans[i] = 1e18;
    }
    memset(mem, -1, sizeof mem);
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0; i<S; ++i) {
        int v = X[i];

        int u = v;

        int no = 0;
        while(u!=-1) {

            long long dis;
            if(mem[v][no]!=-1) dis = mem[v][no];
            else dis = mem[v][no] = get_dist(u, v);

            ans[u] = min(ans[u], dis);
            u = CT_par[u];

            ++no;
        }
    }

    long long ret = 1e18;

    for(int i=0; i<T; ++i) {
        int v = Y[i];

        int u = v;
        int no = 0;
        while(u!=-1) {
            long long dis;
            if(mem[v][no]!=-1) dis = mem[v][no];
            else dis = mem[v][no] = get_dist(u, v);

            ret = min(ret, ans[u] + dis);
            u = CT_par[u];
            ++no;
        }
    }

    for(int i=0; i<S; ++i) {
        int v = X[i];

        int u = v;
        while(u!=-1) {
            ans[u] = 1e18;
            u = CT_par[u];
        }
    }
    return ret;
}

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