제출 #66967

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

factories

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

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

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

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

int dep[500001];
llong dist[500001];
int st[500001];
int ed[500001];
int par[500001][20];
void dfs(int x, int p) {
    static int ord = 0;
    st[x] = ++ord;
    par[x][0] = p;
    for (int i = 1; i < 20; ++i) {
        par[x][i] = par[par[x][i - 1]][i - 1];
    }
    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);
    }
    ed[x] = ord;
}

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);
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i--; ) {
        if ((dep[x] - dep[y]) >> i) x = par[x][i];
    }
    if (x == y) return x;
    for (int i = 20; i--; ) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}

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