Submission #1136256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136256		onlk97	Factories (JOI14_factories)	C++20	100 / 100	4239 ms	304860 KiB

factories

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

vector <pair <int,long long> > g[500010];
int dep[500010];
int in[500010],out[500010],tme;
vector <int> tour;
int f[500010],lg[1000010];
long long dist[500010];
pair <int,int> sp[21][1000010];
void dfs(int cur,int prv){
    if (prv) dep[cur]=dep[prv]+1;
    in[cur]=++tme;
    tour.push_back(cur);
    for (auto i:g[cur]){
        if (i.first==prv) continue;
        dist[i.first]=dist[cur]+i.second;
        dfs(i.first,cur);
        tour.push_back(cur);
    }
    out[cur]=++tme;
}
int lca(int u,int v){
    int pu=f[u],pv=f[v];
    if (pu>pv) swap(pu,pv);
    int l=lg[pv-pu+1];
    pair <int,int> ret=min(sp[l][pu],sp[l][pv-(1<<l)+1]);
    return ret.second;
}
void Init(int N,int A[],int B[],int D[]){
    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]});
    }
    dfs(0,-1);
    int ts=tour.size();
    for (int i=ts-1; i>=0; i--) f[tour[i]]=i;
    for (int i=0; i<ts; i++) sp[0][i]={dep[tour[i]],tour[i]};
    for (int j=1; (1<<j)<=ts; j++){
        for (int i=0; i+(1<<j)-1<ts; i++) sp[j][i]=min(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
    }
    lg[1]=0;
    for (int i=2; i<=ts; i++) lg[i]=lg[i>>1]+1;
}
bool insubtree(int u,int v){
    return in[u]<in[v]&&out[v]<out[u];
}
bool cmp(int u,int v){
    return in[u]<in[v];
}
vector <int> vch[2000010];
int idx,lab[2000010];
long long ca[2000010],cb[2000010],ans;
void dfs2(int cur){
    for (int i:vch[cur]){
        dfs2(i);
        ca[cur]=min(ca[cur],ca[i]+dist[lab[i]]-dist[lab[cur]]);
        cb[cur]=min(cb[cur],cb[i]+dist[lab[i]]-dist[lab[cur]]);
    }
    ans=min(ans,ca[cur]+cb[cur]);
}
long long Query(int S,int X[],int T,int Y[]){
    vector <int> nodes;
    for (int i=0; i<S; i++) nodes.push_back(X[i]);
    for (int i=0; i<T; i++) nodes.push_back(Y[i]);
    nodes.push_back(0);
    sort(nodes.begin(),nodes.end(),cmp);
    int sz=nodes.size();
    for (int i=1; i<sz; i++) nodes.push_back(lca(nodes[i-1],nodes[i]));
    sort(nodes.begin(),nodes.end(),cmp);
    vector <int> tp;
    stack <pair <int,int> > st;
    st.push({0,0});
    map <int,int> mp;
    mp[0]=0;
    for (int i=1; i<nodes.size(); i++){
        if (nodes[i]==nodes[i-1]) continue;
        while (!insubtree(st.top().second,nodes[i])) st.pop();
        vch[st.top().first].push_back(++idx);
        lab[idx]=nodes[i];
        mp[nodes[i]]=idx;
        st.push({idx,nodes[i]});
    }
    for (int i=0; i<=idx; i++) ca[i]=cb[i]=1e18;
    ans=1e18;
    for (int i=0; i<S; i++) ca[mp[X[i]]]=0;
    for (int i=0; i<T; i++) cb[mp[Y[i]]]=0;
    dfs2(0);
    for (int i=0; i<=idx; i++) vch[i].clear();
    idx=0;
    return ans;
}

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