| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 656765 | anhduc2701 | 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<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=1e6+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
set<pair<int,int>>G[500005];
int sz[500005];
int pa[500005];
map<int,long long>dis[500005];
long long ans[500005];
int dfsz(int u,int p){
sz[u]=1;
for(auto v:G[u]){
if(v.first!=p){
sz[u]+=dfsz(v.first,u);
}
}
return sz[u];
}
int centroid(int u,int p,int n){
for(auto v:G[u]){
if(v.first!=p){
if(sz[v.first]>n/2)return centroid(v.first,u,n);
}
}
return u;
}
void dfs2(int u,int p,int c,int d){
dis[c][u]=0;
for(auto v:G[u]){
if(v.first!=p){
dfs2(v.first,u,c,d+v.second);
}
}
}
void upd(int u){
int v=u;
while(v!=0){
ans[v]=min(ans[v],dis[v][u]);
v=pa[v];
}
}
long long query(int u){
long long mi=INF;
int v=u;
while(v!=0){
mi=min(ans[v]+dis[v][u],mi);
v=pa[v];
}
return mi;
}
void build(int u,int p){
int n1=dfsz(u,p);
int c=centroid(u,p,n1);
if(p==-1)p=c;
pa[c]=p;
dfs2(c,p,c,0);
vector<pair<int,int>>tmp(G[c].begin(),G[c].end());
for(auto v:tmp){
G[c].erase({v.first,v.second});
G[v.first].erase({c,v.second});
build(v.first,c);
}
}
void Init(int N,int A[],int B[],int D[]){
n=N;
for(int i=0;i<N;i++){
G[A[i]+1].insert({B[i]+1,D[i]});
G[B[i]+1].insert({A[i]+1,D[i]});
}
build(1,-1);
}
long long Query(int S,int X[],int T,int Y[]){
for(int i=1;i<=n;i++){
ans[i]=INF;
}
for(int i=0;i<S;i++){
upd(X[i]+1);
}
int an=INF;
for(int i=0;i<T;i++){
an=min(an,query(Y[i]+1));
}
return an;
}