| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1253701 | farica | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;
vector<vector<pi>>ancestors, adjL;
vi sz;
vector<bool>is_removed;
int N2;
int get_sz(int pos, int prev = -1) {
sz[pos] = 1;
for(pi adj: adjL[pos]) {
if(adj.first == prev or is_removed[adj.first]) continue;
sz[pos] += get_sz(adj.first, pos);
}
return sz[pos];
}
int get_centroid(int pos, int n, int prev = -1) {
for(pi adj: adjL[pos]) {
if(adj.first == prev or is_removed[adj.first]) continue;
if(sz[adj.first]*2 > n) return get_centroid(adj.first, n, pos);
}
return pos;
}
void get_dists(int pos, int centroid, int prev, int cur_dist) {
for(pi adj: adjL[pos]) {
if(adj.first == prev or is_removed[adj.first]) continue;
get_dists(adj.first, centroid, pos, cur_dist + adj.second);
}
ancestors[pos].push_back({centroid, cur_dist});
}
void build(int pos = 0) {
int centroid = get_centroid(pos, get_sz(pos));
for(pi adj: adjL[centroid]) {
if(is_removed[adj.first]) continue;
get_dists(adj.first, centroid, centroid, adj.second);
}
is_removed[centroid] = 1;
for(pi adj: adjL[centroid]) {
if(is_removed[adj.first]) continue;
build(adj.first);
}
}
void Init(int N, int A[], int B[], int D[]) {
N2 = N;
adjL.assign(N, vector<pi>());
ancestors.assign(N, vector<pi>());
sz.assign(N, 0);
for(int i=0; i<N-1; ++i) {
adjL[A[i]].push_back({B[i], D[i]});
adjL[B[i]].push_back({A[i], D[i]});
}
build();
}
const ll MXVAL = 1e18;
long long Query(int S, int X[], int T, int Y[]) {
vector<ll> min_dist(N2, MXVAL);
for(int i=0; i<S; ++i) {
for(auto &[ancestor, dist]: ancestors[X[i]]) {
min_dist[ancestor] = min(min_dist[ancestor], dist);
}
}
ll ans = 0;
for(int i=0; i<T; ++i) {
ll cnt = MXVAL;
for(auto &[ancestor, dist]: ancestors[Y[i]]) {
if(min_dist[ancestor] == MXVAL) continue;
cnt = min(cnt, dist + min_dist[ancestor]);
}
ans += cnt;
}
return ans;
}