Submission #1230680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230680		BuiDucManh123	Factories (JOI14_factories)	C++17	100 / 100	3454 ms	122564 KiB

factories

#ifndef FACTORIES_H
#define FACTORIES_H
void Init(int N, int A[], int B[], int D[]);

long long Query(int S, int X[], int T, int Y[]);

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

static const int MAXN = 500000;
static const int LG = 20;

int tin[MAXN+5], tout[MAXN+5], depth[MAXN+5];
long long dis[MAXN+5];
int f[MAXN+5][LG];
vector<pair<int,int>> g[MAXN+5];
int tdfs;

void dfs(int u, int p) {
    tin[u] = ++tdfs;
    f[u][0] = p;
    for (auto &e : g[u]) {
        int v = e.first, w = e.second;
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dis[v] = dis[u] + w;
        dfs(v, u);
    }
    tout[u] = tdfs;
}

int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    int diff = depth[x] - depth[y];
    for (int j = 0; j < LG; j++) if (diff >> j & 1) x = f[x][j];
    if (x == y) return x;
    for (int j = LG-1; j >= 0; j--) if (f[x][j] != f[y][j]) {
        x = f[x][j];
        y = f[y][j];
    }
    return f[x][0];
}

void Init(int N, int A[], int B[], int D[]) {
    tdfs = 0;
    for (int i = 0; i < N; i++) {
        g[i].clear(); depth[i] = 0; dis[i] = 0;
        for (int j = 0; j < LG; j++) f[i][j] = 0;
    }
    for (int i = 0; i < N-1; i++) {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
    for (int j = 1; j < LG; j++)
        for (int i = 0; i < N; i++)
            f[i][j] = f[ f[i][j-1] ][j-1];
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> vs;
    vs.reserve(S+T);
    for (int i = 0; i < S; i++) vs.push_back(X[i]);
    for (int i = 0; i < T; i++) vs.push_back(Y[i]);
    sort(vs.begin(), vs.end(), [&](int a, int b){ return tin[a] < tin[b]; });
    int m0 = vs.size();
    for (int i = 1; i < m0; i++)
        vs.push_back(lca(vs[i-1], vs[i]));
    sort(vs.begin(), vs.end(), [&](int a, int b){ return tin[a] < tin[b]; });
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    int M = vs.size();
    unordered_map<int,int> idx;
    for (int i = 0; i < M; i++) idx[vs[i]] = i;
    vector<vector<int>> tree(M);
    vector<int> st;
    st.push_back(vs[0]);
    for (int i = 1; i < M; i++) {
        while (!(tin[st.back()] <= tin[vs[i]] && tout[vs[i]] <= tout[st.back()]))
            st.pop_back();
        int u = st.back(), v = vs[i];
        tree[ idx[u] ].push_back(idx[v]);
        st.push_back(v);
    }
    const long long INF = LLONG_MAX/4;
    vector<long long> fa(M, INF), fb(M, INF);
    for (int i = 0; i < S; i++) fa[ idx[X[i]] ] = 0;
    for (int i = 0; i < T; i++) fb[ idx[Y[i]] ] = 0;
    long long ans = INF;
    function<void(int)> dfsdp = [&](int u) {
        for (int v : tree[u]) {
            dfsdp(v);
            long long d = dis[vs[u]] + dis[vs[v]] - 2*dis[lca(vs[u], vs[v])];
            fa[u] = min(fa[u], fa[v] + d);
            fb[u] = min(fb[u], fb[v] + d);
        }
        ans = min(ans, fa[u] + fb[u]);
    };
    dfsdp(0);
    return ans;
}

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