Submission #1230965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230965		long290429	Factories (JOI14_factories)	C++20	0 / 100	1478 ms	111684 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=4e18;
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 A + B
    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ặ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++){
        vs.push_back(lca(vs[i-1], vs[i]));
    }

    // 3) unique và sort lại
    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
    unordered_map<int,int> idx;
    idx.reserve(sz * 1.3);
    for(int i = 0; i < sz; i++){
        idx[vs[i]] = i;
    }

    // 5) build virtual tree
    vector<vector<pair<int,long long>>> vt(sz);
    vector<int> st; 
    st.reserve(sz);
    for(int i = 0; i < sz; i++){
        int u = vs[i], 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].emplace_back(idu, w);
            vt[idu].emplace_back(top, w);
        }
        st.push_back(idu);
    }

    // 6) multi-source distances
    vector<long long> da(sz, inf), db(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;

    long long ans = inf;
    // post-order DP
    function<void(int,int)> dfs1 = [&](int u, int p){
        for(auto &e : vt[u]){
            int v = e.first; long long 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]);
    };
    // pre-order DP
    function<void(int,int)> dfs2 = [&](int u, int p){
        for(auto &e : vt[u]){
            int v = e.first; long long 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);
        }
    };

    int root = st.front();
    dfs1(root, -1);
    dfs2(root, -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] = 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