| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 6991 | kriii | Factories (JOI14_factories) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "factories.h"
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int cnt,st[500005],ed[500005],par[500005][20],dep[500005]; long long len[500005]; bool chk[500005];
vector<pair<int, int> > grp[500005];
int lca(int x, int y)
{
if (dep[x] > dep[y]) swap(x,y);
int up = dep[y] - dep[x];
for (int i=19;i>=0;i--) if (up & (1 << i)) y = par[y][i];
if (x == y) return x;
for (int i=19;i>=0;i--){
if (par[x][i] != par[y][i]){
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}
void dfs(int x)
{
chk[x] = 1;
for (int i=0;i<grp[x].size();i++){
pair<int, int> = grp[x][i];
if (chk[p.first]) continue;
st[p.first] = ++cnt;
dep[cnt] = dep[st[x]] + 1;
len[cnt] = len[st[x]] + p.second;
par[cnt][0] = st[x];
for (int i=1;i<20;i++) par[cnt][i] = par[par[cnt][i-1]][i-1];
dfs(p.first);
}
ed[st[x]] = cnt;
}
void Init(int N, int A[], int B[], int D[])
{
for (int i=0;i<N-1;i++){
grp[A[i]].push_back(make_pair(B[i],D[i]));
grp[B[i]].push_back(make_pair(A[i],D[i]));
}
st[0] = ++cnt;
dfs(0);
}
int cand[1000000],ext[500005],pcnt; long long U[500005],V[500005],ans;
int pdfs(int x)
{
U[x] = V[x] = 1e16;
if (ext[cand[x]] == 1) U[x] = 0;
if (ext[cand[x]] == 2) V[x] = 0;
int e = x + 1;
while (e < pcnt && cand[e] <= ed[cand[x]]){
int ne = pdfs(e);
U[x] = min(U[x],U[e]+len[cand[e]]-len[cand[x]]);
V[x] = min(V[x],V[e]+len[cand[e]]-len[cand[x]]);
e = ne;
}
ans = min(ans,U[x]+V[x]);
ext[cand[x]] = 0;
return e;
}
long long Query(int S, int X[], int T, int Y[])
{
pcnt = 0;
for (int i=0;i<S;i++) cand[pcnt++] = st[X[i]], ext[st[X[i]]] = 1;
for (int i=0;i<T;i++) cand[pcnt++] = st[Y[i]], ext[st[Y[i]]] = 2;
sort(cand,cand+pcnt);
for (int i=1;i<S+T;i++) cand[pcnt++] = lca(cand[i-1],cand[i]);
sort(cand,cand+pcnt);
pcnt = unique(cand,cand+pcnt) - cand;
ans = 1e16;
pdfs(0);
return ans;
}