| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 117651 | kig9981 | Factories (JOI14_factories) | C++17 | 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 <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[500000];
vector<int> tree[500000];
int query_num, root, depth[500000], parent[500000], P[500000], W[500000], hld[500000], num1[500000], num2[500000];
long long dist[500000], V1[500000], V2[500000];
bool chk[500000];
int set_weight(int c)
{
W[c]=1;
for(auto[n,w]: adj[c]) if(W[n]==0) {
depth[n]=depth[c]+1;
dist[n]=dist[c]+w;
parent[n]=c;
W[c]+=set_weight(n);
}
return W[c];
}
void set_hld(int c)
{
for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>=W[c]) {
hld[n]=hld[c];
set_hld(n);
}
for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]<W[c]) {
hld[n]=n;
set_hld(n);
}
}
int LCA(int a, int b)
{
while(hld[a]!=hld[b]) {
if(depth[hld[a]]<depth[hld[b]]) b=parent[hld[b]];
else a=parent[hld[a]];
}
return depth[a]<depth[b] ? a:b;
}
void reset_weight(int c)
{
W[c]=0;
for(auto[n,w]: adj[c]) if(!chk[n] && W[n]) reset_weight(n);
}
int set_weight2(int c)
{
W[c]=1;
for(auto[n,w]: adj[c]) if(!chk[n] && W[n]==0) W[c]+=set_weight2(n);
return W[c];
}
int get_mid(int c, int r)
{
bool valid=true;
int t;
if(W[r]>=2*W[c]) valid=false;
for(auto[n,w]: adj[c]) if(!chk[n] && W[n]<W[c]) {
if((t=get_mid(n,r))!=-1) return t;
if(2*W[n]>=W[r]) valid=false;
}
return valid ? c:-1;
}
int get_centroid(int c)
{
int nxt;
reset_weight(c), set_weight2(c);
chk[c=get_mid(c,c)]=true;
for(auto[n,w]: adj[c]) if(!chk[n]) {
tree[c].push_back(nxt=get_centroid(n));
P[nxt]=c;
}
return c;
}
void init(int N, vector<int> A, vector<int> B, vector<int> D)
{
for(int i=0;i<N-1;i++) {
adj[A[i]].emplace_back(B[i],D[i]);
adj[B[i]].emplace_back(A[i],D[i]);
}
set_weight(0); set_hld(0);
root=get_centroid(0);
}
long long Query(int S, vector<int> X, int T, vector<int> Y)
{
long long ret=0x7fffffffffffffffLL;
query_num++;
for(int i=0;i<S;i++) {
for(int j=X[i];j!=root;j=P[j]) {
if(num1[j]==query_num) V1[j]=min(V1[j],dist[X[i]]+dist[j]-2*dist[LCA(X[i],j)]);
else {
num1[j]=query_num;
V1[j]=dist[X[i]]+dist[j]-2*dist[LCA(X[i],j)];
}
}
if(num1[root]==query_num) V1[root]=min(V1[root],dist[X[i]]+dist[root]-2*dist[LCA(X[i],root)]);
else {
num1[root]=query_num;
V1[root]=dist[X[i]]+dist[root]-2*dist[LCA(X[i],root)];
}
}
for(int i=0;i<T;i++) {
for(int j=Y[i];j!=root;j=P[j]) {
if(num1[j]!=query_num) continue;
if(num2[j]==query_num) V2[j]=min(V2[j],dist[Y[i]]+dist[j]-2*dist[LCA(Y[i],j)]);
else {
num2[j]=query_num;
V2[j]=dist[Y[i]]+dist[j]-2*dist[LCA(Y[i],j)];
}
ret=min(ret,V1[j]+V2[j]);
}
if(num2[root]==query_num) V2[root]=min(V2[root],dist[Y[i]]+dist[root]-2*dist[LCA(Y[i],root)]);
else {
num2[root]=query_num;
V2[root]=dist[Y[i]]+dist[root]-2*dist[LCA(Y[i],root)];
}
}
return min(ret,V1[root]+V2[root]);
}