제출 #1154887

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

factories

#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
using namespace std;

const int N = 5e5 + 5;
const ll oo = 1e18;
int n, q, tin[N], tout[N], h[N], timer, up[N][25];
vector<ii> g[N];
ll sum[N];
vector<pair<int, ll>> g2[N];
int type[N];
ll res, dp[N][5];

void dfs2(int u){
    dp[u][0] = dp[u][1] = oo;
    if(type[u] != -1){
        dp[u][type[u]] = 0;
    }
    for(pair<int,ll> tmp : g2[u]){
        int v = tmp.fi;
        ll c = tmp.se;
        dfs2(v);
        res = min(res,
                  min(dp[u][0] + c + dp[v][1], dp[u][1] + c + dp[v][0]));
        for(int t = 2; t--;){
            dp[u][t] = min(dp[u][t], dp[v][t] + c);
        }
    }
}

void dfs(int u, int cur_par = -1){
    tin[u] = ++timer;
    for(ii tmp : g[u]){
        int v = tmp.fi, c = tmp.se;
        if(v == cur_par) continue;
        sum[v] = sum[u] + c;
        h[v] = h[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
    tout[u] = timer;
}
void build_lca(){
    h[1] = 1;
    sum[1] = 0;
    dfs(1);
    for(int j = 1; j <= 19; j++){
        for(int i = 1; i <= n; i++){
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
}
int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    for(int j = 19; j >= 0; j--){
        if(h[up[u][j]] >= h[v])
            u = up[u][j];
    }
    if(u == v) return u;
    for(int j = 19; j >= 0; j--){
        if(up[u][j] != up[v][j]){
            u = up[u][j];
            v = up[v][j];
        }
    }
    return up[u][0];
}
bool anc(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tin[v];
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0; i < n - 1; i++){
        A[i]++; B[i]++;
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    // for(int i = 1; i <= n; i++){
    //     cout << i << ' ';
    //     for(ii x : g[i]) cout << x.fi << ' ';
    //     cout << '\n';
    // }
    build_lca();
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<ii> ord;
    for(int i = 0; i < S; i++) X[i]++;
    for(int i = 0; i < T; i++) Y[i]++;
    
    for(int i = 0; i < S; i++)
        ord.emplace_back(tin[X[i]], X[i]);
    for(int i = 0; i < T; i++)
        ord.emplace_back(tin[Y[i]], Y[i]);
    sort(ord.begin(), ord.end());
    for(int i = 0, sz = ord.size(); i < sz - 1; i++){
        int x = lca(ord[i].se, ord[i + 1].se);
        // cout << ord[i].se << ' ' << ord[i + 1].se << ' ' << x << '\n';
        ord.emplace_back(tin[x], x);
    }
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    stack<int> st;
    for(ii x : ord){
        g2[x.se].clear();
        type[x.se] = -1;
    }
    for(int i = 0; i < S; i++)
        type[X[i]] = 0;
    for(int i = 0; i < T; i++)
        type[Y[i]] = 1;
    for(ii pi : ord){
        int c = pi.se;
        while(!st.empty() && !anc(st.top(), c)){
            st.pop();
        }
        if(!st.empty()){
            int r = st.top();
            g2[r].emplace_back(c, sum[c] - sum[r]);
//            g2[c].emplace_back(r, sum[c] - sum[r]);
        }
        st.push(c);
    }
    // for(int i = 0; i < ord.size(); i++){
    //     cout << ord[i].se << ": ";
    //     for(pair<long long, int> x : g2[ord[i].se])
    //         cout << x.fi << ' ' << x.se << ", ";
    //     cout << '\n';
    // }
    int root = ord.front().se;
    // cout << root << '\n';
    res = oo;
    dfs2(root);
    return res;
}

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