제출 #780097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780097		huutuan	공장들 (JOI14_factories)	C++14	100 / 100	2274 ms	454952 KiB

factories

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

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=5e5+1, LG=20;
int n, nvt, tdfs, st_cnt, tin[N], tout[N], dep[N], pos_st[N], dis[N], color[N];
pair<int, int> st[N*2][LG];
vector<pair<int, int>> g[N], vt[N];

void pre_dfs(int u, int p){
    tin[u]=++tdfs;
    st[++st_cnt][0]={dep[u], u};
    pos_st[u]=st_cnt;
    for (auto& e:g[u]){
        int v=e.first, w=e.second;
        if (v==p) continue;
        dep[v]=dep[u]+1;
        dis[v]=dis[u]+w;
        pre_dfs(v, u);
        st[++st_cnt][0]={dep[u], u};
    }
    tout[u]=tdfs;
}

void build_st(){
    for (int k=1; k<LG; ++k){
        for (int l=1; l+(1<<k)-1<=st_cnt; ++l){
            st[l][k]=min(st[l][k-1], st[l+(1<<(k-1))][k-1]);
        }
    }
}

int lca(int u, int v){
    u=pos_st[u], v=pos_st[v];
    if (u>v) swap(u, v);
    int lg=__lg(v-u+1);
    return min(st[u][lg], st[v-(1<<lg)+1][lg]).second;
}

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

void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    memset(color, -1, sizeof color);
    n=N;
    for (int i=0; i<n-1; ++i){
        ++A[i]; ++B[i];
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }
    pre_dfs(1, 0);
    build_st();
}

pair<int, int> dfs(int u, int p, int& ans){
    pair<int, int> wtf={1e18, 1e18};
    if (color[u]==0) wtf.first=0;
    else if (color[u]==1) wtf.second=0;
    for (auto& e:vt[u]){
        int v=e.first, w=e.second;
        if (v==p) continue;
        auto lmao=dfs(v, u, ans);
        wtf.first=min(wtf.first, lmao.first+w);
        wtf.second=min(wtf.second, lmao.second+w);
    }
    ans=min(ans, wtf.first+wtf.second);
    return wtf;
}

long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
    vector<int> vtn;
    for (int i=0; i<S; ++i) ++X[i], color[X[i]]=0;
    for (int i=0; i<T; ++i) ++Y[i], color[Y[i]]=1;
    for (int i=0; i<S; ++i) vtn.push_back(X[i]);
    for (int i=0; i<T; ++i) vtn.push_back(Y[i]);
    sort(all(vtn), [&](int u, int v) -> bool {
        return tin[u]<tin[v];
    });
    for (int i=0; i<S+T-1; ++i) vtn.push_back(lca(vtn[i], vtn[i+1]));
    sort(all(vtn), [&](int u, int v) -> bool {
        return tin[u]<tin[v];
    });
    vtn.resize(unique(all(vtn))-vtn.begin());
    for (int i:vtn) vt[i].clear();
    stack<int> st;
    for (int i:vtn){
        while (st.size() && !is_ancestor(st.top(), i)) st.pop();
        if (st.empty()) st.push(i);
        else{
            vt[st.top()].emplace_back(i, dis[i]-dis[st.top()]);
            vt[i].emplace_back(st.top(), dis[i]-dis[st.top()]);
            st.push(i);
        }
    }
    int ans=1e18;
    dfs(vtn[0], 0, ans);
    for (int i=0; i<S; ++i) color[X[i]]=-1;
    for (int i=0; i<T; ++i) color[Y[i]]=-1;
    return ans;
}

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