제출 #1230975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230975		bb2009	공장들 (JOI14_factories)	C++20	33 / 100	1845 ms	157092 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define roadtovoai ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define first fi
#define second se
#define pb push_back
#define eb emplace_back
const int MAXN = 5e5+5;
const long long INF = 1e18;
int depth[MAXN],  par[MAXN][20]; // par[i][j] = to tien cua dinh i sau 2^j buoc di tren cay
long long tin[MAXN], tout[MAXN], timer, dist[MAXN], dp[MAXN];
bool visited[MAXN];
vector<pair<int ,int>> adj[MAXN];
vector<pair<long long,long long>> vt[MAXN];
void dfs(int u, int e){
    par[u][0] = e;
    tin[u] = ++timer;
    for(int i=1; i<=17; i++){
        par[u][i] = par[par[u][i-1]][i-1];
    }
    for(auto [to, w] : adj[u]){
        if(to == e) continue;
        depth[to] = depth[u] + 1;
        dist[to] = dist[u] + w;
        dfs(to, u);
    }
    tout[u] = timer;
}
bool vtsort(long long u, long long v){
    return tin[u] < tin[v];
}
bool check(long long u, long long v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int u, int v){
    if(check(u,v)) return u;
    if(check(v,u)) return v;
    for(int i=17; i>=0; i--){
        if(depth[u] >= (1<<i) && !check(par[u][i], v)){
            u = par[u][i];
        }
    }
    return par[u][0];
}
long long get(int u,int v){
    int tt = LCA(u,v);
    return dist[u] + dist[v] - 2*dist[tt];
}
void Init(int n, int A[], int B[], int D[]){
    for(int i=0; i<n-1; i++){
        adj[A[i]].pb({B[i], D[i]});
        adj[B[i]].pb({A[i], D[i]});
    }
    for(int i=0; i<=17; i++){
        par[0][i] = 0;
    }
    depth[0] = 0;
    dist[0] = 0;
    dfs(0, 0);
    memset(dp, -1, sizeof(dp));
}
long long Query(int S, int X[], int T, int Y[]){
    vector<long long> sp;
    for(int i=0; i<S; i++){
        sp.pb(X[i]);
    }
    for(int i=0; i<T; i++){
        sp.pb(Y[i]);
        dp[Y[i]] = 0;
    }
    sort(sp.begin(), sp.end(), vtsort);
    vector<long long> node = sp;
    for(int i=1; i<sp.size();i++){
        node.pb(LCA(sp[i-1], sp[i]));
    }
    sort(node.begin(), node.end(), vtsort);
    node.erase(unique(node.begin(),node.end()), node.end());
    stack<long long> st;
    st.push(node[0]);
    for(int i=1; i<node.size(); i++){
        long long u = node[i];
        while(!check(st.top(),u)){
            st.pop();
        }
        long long v = st.top();
        long long d = get(u, v);
        vt[u].pb({v, d});
        vt[v].pb({u,d});
        st.push(u);
    }
    priority_queue<pair<long long,long long>, vector<pair<long long,long long>>, greater<pair<long long ,long long>>> pq;
    for(int i=0; i<S; i++){
        pq.push({0, X[i]});
    }
    long long ans = INF;
    while(!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if(visited[u]) continue;
        visited[u] = true;
        if(dp[u] == 0){
            ans = d;
            break;
        }
        for(auto [to, w] : vt[u]){
            if(!visited[to]) pq.push({d+w, to});
        }
    }
    for(long long u : node){
        vt[u].clear();
        visited[u] = false;
        dp[u] = -1;
    }
    return ans;
}

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