제출 #66965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66965		imeimi2000	공장들 (JOI14_factories)	C++17	0 / 100	34 ms	12664 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;
vector<int> qs;
llong ans;
pll dfs2() {
    llong d = dist[qs[idx]];
    llong mx = d + ((in[qs[idx]] & 1) ? 0 : inf);
    llong my = d + ((in[qs[idx]] >> 1) ? 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[]) {
    qs.clear();
    for (int i = 0; i < S; ++i) {
        in[++X[i]] = 0;
    }
    for (int i = 0; i < T; ++i) {
        in[++Y[i]] = 0;
    }
    for (int i = 0; i < S; ++i) {
        qs.push_back(X[i]);
        in[X[i]] ^= 1;
    }
    for (int i = 0; i < T; ++i) {
        qs.push_back(Y[i]);
        in[Y[i]] ^= 2;
    }
    sort(qs.begin(), qs.end(), [&](int i, int j) { return st[i] < st[j]; });
    m = qs.size();
    for (int i = 1; i < m; ++i) {
        qs.push_back(lca(qs[i - 1], qs[i]));
    }
    sort(qs.begin(), qs.end(), [&](int i, int j) { return st[i] < st[j]; });
    qs.erase(unique(qs.begin(), qs.end()), qs.end());
    m = qs.size();
    
    idx = 0;
    ans = inf;
    dfs2();
    return ans;
}

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