제출 #1370667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370667		husseinjuanda	공장들 (JOI14_factories)	C++20	100 / 100	1603 ms	131268 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

const int MAXN = 500000 + 5;
const int LOG = 20;
const long long INF = (long long)4e18;

int n;
vector<pair<int,int>> g[MAXN];
vector<pair<int,long long>> vt[MAXN];

int tin[MAXN], tout[MAXN], timer_;
int depth_[MAXN];
int up[MAXN][LOG];
long long dist_root[MAXN];

int color[MAXN];
long long bestX[MAXN], bestY[MAXN];

bool is_ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v){
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;

    for(int i = LOG - 1; i >= 0; i--){
        if(!is_ancestor(up[u][i], v)){
            u = up[u][i];
        }
    }

    return up[u][0];
}

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

void Init(int N, int A[], int B[], int D[]){
    n = N;

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

    vector<int> it(n, 0), par(n, -1);
    stack<int> st;

    par[0] = 0;
    up[0][0] = 0;
    for(int j = 1; j < LOG; j++) up[0][j] = 0;

    tin[0] = timer_++;
    st.push(0);

    while(!st.empty()){
        int u = st.top();

        if(it[u] == (int)g[u].size()){
            tout[u] = timer_;
            st.pop();
            continue;
        }

        auto [v, w] = g[u][it[u]++];
        if(v == par[u]) continue;

        par[v] = u;
        depth_[v] = depth_[u] + 1;
        dist_root[v] = dist_root[u] + w;

        up[v][0] = u;
        for(int j = 1; j < LOG; j++){
            up[v][j] = up[up[v][j - 1]][j - 1];
        }

        tin[v] = timer_++;
        st.push(v);
    }
}

long long Query(int S, int X[], int T, int Y[]){
    vector<int> nodes;
    nodes.reserve(2 * (S + T));

    vector<int> marked;
    marked.reserve(S + T);

    for(int i = 0; i < S; i++){
        color[X[i]] = 1;
        nodes.push_back(X[i]);
        marked.push_back(X[i]);
    }

    for(int i = 0; i < T; i++){
        color[Y[i]] = 2;
        nodes.push_back(Y[i]);
        marked.push_back(Y[i]);
    }

    sort(nodes.begin(), nodes.end(), [&](int a, int b){
        return tin[a] < tin[b];
    });

    int m = nodes.size();

    for(int i = 0; i + 1 < m; i++){
        nodes.push_back(lca(nodes[i], nodes[i + 1]));
    }

    sort(nodes.begin(), nodes.end(), [&](int a, int b){
        return tin[a] < tin[b];
    });

    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());

    for(int u : nodes){
        vt[u].clear();
        bestX[u] = INF;
        bestY[u] = INF;
    }

    vector<int> stk;

    for(int u : nodes){
        if(stk.empty()){
            stk.push_back(u);
            continue;
        }

        while(!is_ancestor(stk.back(), u)){
            stk.pop_back();
        }

        int p = stk.back();
        vt[p].push_back({u, dist_root[u] - dist_root[p]});

        stk.push_back(u);
    }

    for(int u : nodes){
        if(color[u] == 1) bestX[u] = 0;
        if(color[u] == 2) bestY[u] = 0;
    }

    long long ans = INF;

    for(int i = (int)nodes.size() - 1; i >= 0; i--){
        int u = nodes[i];

        for(auto [v, w] : vt[u]){
            if(bestX[u] < INF / 2 && bestY[v] < INF / 2){
                ans = min(ans, bestX[u] + bestY[v] + w);
            }

            if(bestY[u] < INF / 2 && bestX[v] < INF / 2){
                ans = min(ans, bestY[u] + bestX[v] + w);
            }

            bestX[u] = min(bestX[u], bestX[v] + w);
            bestY[u] = min(bestY[u], bestY[v] + w);
        }
    }

    for(int u : marked){
        color[u] = 0;
    }

    return ans;
}

• 서브태스크 1: 15 / 15
• 서브태스크 2: 18 / 18
• 서브태스크 3: 67 / 67