제출 #1230678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230678		BuiDucManh123	Factories (JOI14_factories)	C++20	33 / 100	8084 ms	116644 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 = 500005;
static const int LG = 20;

int N;
vector<pair<int,int>> g[MAXN];
int f[MAXN][LG];
int depth[MAXN];
int tin[MAXN], tout[MAXN], tmr;
long long dis[MAXN];

void dfs(int u, int p) {
    tin[u] = ++tmr;
    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] = tmr;
}

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

long long distBetween(int u, int v) {
    int w = lca(u, v);
    return dis[u] + dis[v] - 2*dis[w];
}

void Init(int NN, int A[], int B[], int D[]) {
    N = NN;
    for (int i = 0; i < N; i++) {
        g[i].clear();
        dis[i] = 0;
        depth[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]});
    }
    tmr = 0;
    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();
    vector<vector<int>> adj(M);
    vector<int> stk;
    stk.push_back(vs[0]);
    for (int i = 1; i < M; i++) {
        while (!(tin[stk.back()] <= tin[vs[i]] && tout[vs[i]] <= tout[stk.back()]))
            stk.pop_back();
        int u = stk.back(), v = vs[i];
        int iu = lower_bound(vs.begin(), vs.end(), u, [&](int a,int b){return tin[a]<tin[b];}) - vs.begin();
        int iv = lower_bound(vs.begin(), vs.end(), v, [&](int a,int b){return tin[a]<tin[b];}) - vs.begin();
        adj[iu].push_back(iv);
        stk.push_back(vs[i]);
    }
    const long long INF = LLONG_MAX/4;
    vector<long long> fa(M, INF), fb(M, INF);
    for (int i = 0; i < M; i++) {
        if (find(X, X+S, vs[i]) != X+S) fa[i] = 0;
        if (find(Y, Y+T, vs[i]) != Y+T) fb[i] = 0;
    }
    long long ans = INF;
    function<void(int)> dfsdp = [&](int u){
        for (int v : adj[u]) {
            dfsdp(v);
            long long d = distBetween(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: 0 / 67