| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1258867 | khoavn2008 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define REP(i,r) for(ll i=0,_r=(r);i<_r;i++)
#define FOR(i,l,r) for(ll i=(l),_r=(r);i<=_r;i++)
#define FORE(i,v) for(__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define FORNG(i,r,l) for(ll i=(r),_l=(l);i>=_l;i--)
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1LL)
#define all(v) (v).begin(),(v).end()
#define size(v) ((ll)(v).size())
const ll MOD = 1e9+7, N = 5e5+10, INF = 1e18, LOG = 20;
ll n,q,d[N],sz[N];
vector<pair<ll,ll>> adj[N],cen_par[N];
bool del[N];
ll get_sz(ll u,ll par = -1){
sz[u] = 1;
for(auto [v, w] : adj[u]){
if(v == par || del[v])continue;
sz[u] += get_sz(v, u);
}
return sz[u];
}
ll find_centroid(ll u,ll par,ll cur_sz){
for(auto [v, w] : adj[u]){
if(v == par || del[v])continue;
if(sz[v] * 2 > cur_sz)return find_centroid(v, u, cur_sz);
}
return u;
}
void dfs(ll u,ll par,ll cen,ll high){
cen_par[u].pb({cen, high});
for(auto [v, w] : adj[u]){
if(v == par || del[v])continue;
dfs(v, u, cen, high + w);
}
}
void centroid_dcp(ll u){
ll root = find_centroid(u, -1, get_sz(u));
del[root] = 1;
dfs(root, -1, root, 0);
for(auto [v, w] : adj[root])if(!del[v])centroid_dcp(v);
}
ll query(ll s,ll x[],ll t,ll y[]){
ll res = INF;
REP(i, s){
ll u = x[i];
for(auto [cen, dist] : cen_par[u]){
d[cen] = min(d[cen], dist);
}
}
REP(i, t){
ll u = y[i];
for(auto [cen, dist] : cen_par[u]){
res = min(res, dist + d[cen]);
}
}
REP(i, s){
ll u = x[i];
for(auto [cen, dist] : cen_par[u]){
d[cen] = INF;
}
}
return res;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
REP(i,n)adj[A[i]].pb({B[i], D[i]}),adj[B[i]].pb({A[i], D[i]});
centroid_dcp(0);
}