제출 #367187

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

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

#define SZ(x)                   (int) x.size()
#define F                       first
#define S                       second

const int N = 5e5 + 10;
int M[N], from[N], to[N], w[N], P[20][N], H[N], St[N], Ft[N], n, tim; vector<int> adj[N]; ll S[N], dp1[N], dp2[N];

void preDFS(int v, int p = -1) {
    St[v] = tim++;
    for (int i = 1; i < 20; i++) 
        P[i][v] = P[i - 1][P[i - 1][v]];
    for (int id : adj[v]) {
        int u = from[id] ^ to[id] ^ v;
        if (u != p) S[u] = S[v] + w[id], H[u] = H[v] + 1, P[0][u] = v, preDFS(u, v);
    }
    Ft[v] = tim;
}

int getpar(int v, int h) {
    for (int i = h; i; i -= i & -i) 
        v = P[__builtin_ctz(i)][v];
    return v;
}

int LCA(int v, int u) {
    if (H[u] < H[v]) swap(u, v);
    u = getpar(u, H[u] - H[v]);
    for (int i = 19; ~i; i--) 
        if (P[i][v] != P[i][u]) 
            u = P[i][u], v = P[i][v];
    return u == v ? v : P[0][v];
}

void downDFS(int v) { 
    if (M[v]) dp1[v] = 0;
    for (int u : adj[v]) {
        downDFS(u);
        if (dp1[u] < 1e18) dp1[v] = min(dp1[v], dp1[u] + S[u] - S[v]);
    }
}

void upd(pair<pair<ll, ll>, pair<ll, ll>> &x, ll v, ll y) {
    x.S = min(x.S, {y, v});
    if (x.F > x.S) swap(x.S, x.F);
}

void upDFS(int v) {
    if (M[v]) dp2[v] = 0;
    pair<pair<ll, ll>, pair<ll, ll>> x = {{1e16, 1e16}, {1e16, 1e16}};
    upd(x, v, dp2[v]); 
    for (int u : adj[v]) {
        upd(x, u, dp1[u] + S[u] - S[v]);
    }
    for (int u : adj[v]) {
        if (x.F.S == u) dp2[u] = x.S.F + S[u] - S[v];
        else dp2[u] = x.F.F + S[u] - S[v];
        dp2[u] = min(dp2[u], (ll) 1e18);
    }
    for (int u : adj[v]) upDFS(u);
}   

void Init(int _n, int A[], int B[], int D[]) {
    n = _n;
    for (int i = 0; i + 1 < n; i++) {
        from[i] = A[i], to[i] = B[i], w[i] = D[i];
        adj[from[i]].push_back(i);
        adj[to[i]].push_back(i);
    }
    preDFS(0);
    for (int i = 0; i < n; i++) adj[i] = {};
    for (int i = 0; i < n; i++) dp1[i] = dp2[i] = 1e18;
}

ll Query(int s, int X[], int t, int Y[]) {
    vector<int> vec;
    for (int i = 0; i < s; i++) vec.push_back(X[i]);
    for (int i = 0; i < t; i++) vec.push_back(Y[i]), M[Y[i]] = 1;
    sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; });
    int k = SZ(vec);
    for (int i = 0; i < k; i++) {
        int p = LCA(vec[i], vec[(i + 1) % k]);
        vec.push_back(p);
    }
    sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; });
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    vector<int> st = {vec[0]};
    for (int i = 1; i < SZ(vec); i++) {
        int v = vec[i];
        while (St[st.back()] > St[v] || Ft[v] > Ft[st.back()]) 
            st.pop_back();
        assert(SZ(st));
        adj[st.back()].push_back(v);
        st.push_back(v);
    }   
    downDFS(vec[0]);
    upDFS(vec[0]);
    ll ret = 1e18;
    for (int i = 0; i < s; i++) ret = min(ret, min(dp1[X[i]], dp2[X[i]]));
    for (int i = 0; i < SZ(vec); i++) dp1[vec[i]] = dp2[vec[i]] = 1e18, adj[vec[i]] = {};
    for (int i = 0; i < t; i++) M[Y[i]] = 0;
    return ret;
}

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