Submission #1230957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230957		long290429	Factories (JOI14_factories)	C++20	0 / 100	1822 ms	111672 KiB

factories

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int tin[maxn],tout[maxn];
int dep[maxn],dtr[maxn];
vector<pair<int,int>> adj[maxn];
int tt,lg;
vector<vector<int>> up;
long long inf=LLONG_MAX/4,ans;
void dfs(int u,int par) {
  tin[u]=++tt;
  up[u][0]=par;
  for(int i=1;i<=lg;++i) {
    if(up[u][i-1]!=-1) {
      up[u][i]=up[up[u][i-1]][i-1];
    }
    else break;
  }
  for(pair<int,int> p:adj[u]) {
    int v=p.first,w=p.second;
    if(v==par) continue;
    dep[v]=dep[u]+1;
    dtr[v]=dtr[u]+w;
    dfs(v,u);
  }
  tout[u]=tt;
}
int lca(int u,int v) {
  if(dep[u]<dep[v]) swap(u,v);
  int k=dep[u]-dep[v];
  for(int i=0;k>0;++i) {
    if(k&1) {
      u=up[u][i];
    }
    k>>=1;
  }
  if(u==v) return u;
  for(int i=lg;i>=0;--i) {
    if(up[u][i]!=-1&&up[v][i]!=-1&&up[u][i]!=up[v][i]) {
      u=up[u][i];
      v=up[v][i];
    }
  }
  return up[u][0];
}
long long solve(int a[], int n, int b[], int m) {
    // 1) gom tất cả nút của A và B vào cùng 1 vector
    vector<int> vs;
    vs.reserve(n + m);
    for(int i = 0; i < n; i++) vs.push_back(a[i]);
    for(int i = 0; i < m; i++) vs.push_back(b[i]);

    // 2) sort theo tin và thêm LCA của các cặp liền kề
    sort(vs.begin(), vs.end(), [&](int u, int v){
        return tin[u] < tin[v];
    });
    int K = vs.size();
    for(int i = 1; i < K; i++){
        int u = vs[i-1], v = vs[i];
        vs.push_back(lca(u, v));
    }

    // 3) unique lại và sort theo tin nữa
    sort(vs.begin(), vs.end(), [&](int u, int v){
        return tin[u] < tin[v];
    });
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    int sz = vs.size();

    // 4) đánh số lại (node -> idx)
    unordered_map<int,int> idx;
    idx.reserve(sz * 1.3);
    vector<vector<pair<int,int>>> vt(sz);
    for(int i = 0; i < sz; i++){
        idx[vs[i]] = i;
        vt[i].clear();
    }

    // 5) build virtual tree bằng stack
    static vector<int> st;
    
    st.clear();
    for(int i = 0; i < sz; i++){
        int u = vs[i];
        int idu = i;
        while(!st.empty()){
            int top = st.back();
            int v = vs[top];
            if(tin[v] <= tin[u] && tout[u] <= tout[v]) break;
            st.pop_back();
        }
        if(!st.empty()){
            int top = st.back();
            int v = vs[top];
            long long w = dtr[u] - dtr[v];
            vt[top].push_back({idu, (int)w});
            vt[idu].push_back({top, (int)w});
        }
        st.push_back(idu);
    }

    // 6) multi-source init
    const long long INF = LLONG_MAX/4;
    static vector<long long> da, db;
    da.assign(sz, INF);
    db.assign(sz, INF);
    for(int i = 0; i < n; i++) da[idx[a[i]]] = 0;
    for(int i = 0; i < m; i++) db[idx[b[i]]] = 0;

    // 7) two-pass DP trên cây để lấy min(da[x]+db[x])
    long long ans = INF;
    function<void(int,int)> dfs1 = [&](int u, int p){
        for(auto &e : vt[u]){
            int v = e.first, w = e.second;
            if(v == p) continue;
            dfs1(v, u);
            da[u] = min(da[u], da[v] + w);
            db[u] = min(db[u], db[v] + w);
        }
        ans = min(ans, da[u] + db[u]);
    };
    function<void(int,int)> dfs2 = [&](int u, int p){
        for(auto &e : vt[u]){
            int v = e.first, w = e.second;
            if(v == p) continue;
            da[v] = min(da[v], da[u] + w);
            db[v] = min(db[v], db[u] + w);
            ans = min(ans, da[v] + db[v]);
            dfs2(v, u);
        }
    };
    // st[0] chứa idx của nút có tin nhỏ nhất => gốc virtual tree
    dfs1(st[0], -1);
    dfs2(st[0], -1);

    return ans;
}
void Init(int n,int u[],int v[],int w[]) {
  for(int i=0;i<n;++i) adj[i].clear();
  for(int i=0;i<n-1;++i) {
    adj[u[i]].push_back({v[i],w[i]});
    adj[v[i]].push_back({u[i],w[i]});
  }
  tt=0;
  dep[0]=0;
  dtr[0]=0;
  lg=floor(log2(n));
  up.assign(n,vector<int>(lg+1,-1));
  dfs(0,-1);
}
long long Query(int s,int x[],int t,int y[]) {
  return solve(x,s,y,t);
}

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