| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1230963 | long290429 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#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 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);
}