제출 #66982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66982		imeimi2000	공장들 (JOI14_factories)	C++17	100 / 100	3020 ms	295328 KiB

factories

#include "factories.h"
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

struct _edge {
    int x, d;
    _edge(int x, int d) : x(x), d(d) {}
};

int n, k;
vector<_edge> edge[500001];

int dep[500001];
llong dist[500001];
int st[500001];
int ed[500001];
int ord[1000000];
pii seg[1000000][21];
int pw[1000001];
int sz;
void dfs(int x, int p) {
    ord[st[x] = k++] = x;
    for (_edge i : edge[x]) {
        if (i.x == p) continue;
        dep[i.x] = dep[x] + 1;
        dist[i.x] = dist[x] + i.d;
        dfs(i.x, x);
        ord[k++] = x;
    }
    ed[x] = k;
}

void init() {
    for (int i = 1, j = 0; i <= 1000000; ++i) {
        if ((1 << (j + 1)) < i) ++j;
        pw[i] = j;
    }
    for (int i = 0; i < k; ++i) {
        seg[i][0] = pii(dep[ord[i]], ord[i]);
    }
    for (int i = 1; i < 21; ++i) {
        for (int j = 0; j < k; ++j) {
            seg[j][i] = seg[j][i - 1];
            if (j + (1 << (i - 1)) < k) {
                seg[j][i] = min(seg[j][i], seg[j + (1 << (i - 1))][i - 1]);
            }
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; ++i) {
        ++A[i]; ++B[i];
        edge[A[i]].emplace_back(B[i], D[i]);
        edge[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(1, 0);
    init();
}

int lca(int x, int y) {
    if (x == y) return x;
    x = st[x]; y = st[y];
    if (x > y) swap(x, y);
    int t = pw[y - x + 1];
    return min(seg[x][t], seg[y - (1 << t) + 1][t]).second;
}

const llong inf = 1e16;
int in[500001];
int m, idx;
int qs[1000000];
llong ans;
pll dfs2() {
    llong d = dist[qs[idx]];
    llong mx = d + ((in[qs[idx]] == 1) ? 0 : inf);
    llong my = d + ((in[qs[idx]] == 2) ? 0 : inf);
    
    int e = ed[qs[idx++]];
    while (idx < m) {
        if (e < st[qs[idx]]) break;
        llong rx, ry;
        
        tie(rx, ry) = dfs2();
        ans = min({ ans, mx + ry - d - d, my + rx - d - d });
        mx = min(mx, rx);
        my = min(my, ry);
    }
    return pll(mx, my);
}

llong Query(int S, int X[], int T, int Y[]) {
    m = 0;
    for (int i = 0; i < S; ++i) {
        qs[m++] = ++X[i];
    }
    for (int i = 0; i < T; ++i) {
        qs[m++] = ++Y[i];
    }
    
    sort(qs, qs + m, [&](int i, int j) { return st[i] < st[j]; });
    for (int i = 0; i + 1 < m; ++i) {
        qs[m + i] = lca(qs[i], qs[i + 1]);
    }
    m = (m << 1) - 1;
    sort(qs, qs + m, [&](int i, int j) { return st[i] < st[j]; });
    m = unique(qs, qs + m) - qs;
    
    for (int i = 0; i < m; ++i) in[qs[i]] = 0;
    for (int i = 0; i < S; ++i) in[X[i]] = 1;
    for (int i = 0; i < T; ++i) in[Y[i]] = 2;
    
    idx = 0;
    ans = inf;
    dfs2();
    return ans;
}

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