| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1281755 | ducanh0811 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
// 🌲🌲🌲🌲🌲🌳🌳🌳🌳🌳🌳🌴🌴🌴🌴🌴🌴🌴🌴
#include <bits/stdc++.h>
bool M1;
#include "factories.h"
#define FOR(i, a, b) for (long long i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (long long i = (a), _b = (b); i >= _b; --i)
using namespace std;
#define MAXN 500005
#define MAXQ 100005
long long n, q;
vector<pair<long long, long long>> g[MAXN];
bool blocked[MAXN];
long long sz[MAXN];
long long par[MAXN];
long long dep[MAXN];
long long sumWeight[MAXN];
long long curWeight[MAXN];
long long up[MAXN][20];
long long bestVal[MAXN];
const long long INF = 1e15;
///++++++++++++++++++++++++++++++++++++++///
void minimize(long long &a, const long long &b) {
if (a > b) a = b;
}
void preCalc(long long u, long long p) {
for (pair<long long, long long> &x : g[u]) {
long long v, w; tie(v, w) = x;
if (v == p) continue;
up[v][0] = u;
dep[v] = dep[u] + 1;
sumWeight[v] = sumWeight[u] + w;
curWeight[v] = w;
preCalc(v, u);
}
}
void prepareLCA() {
FOR(j, 1, 19) FOR(i, 1, n) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
long long LCA(long long a, long long b) {
if (dep[a] < dep[b]) swap(a, b);
long long h = dep[a] - dep[b];
for (long long i = 0; (1 << i) <= h; ++i) {
if (h >> i & 1) a = up[a][i];
}
if (a == b) return a;
h = __lg(dep[a]);
for (long long i = h; i >= 0; --i) {
if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
long long dist(long long a, long long b) {
long long lca = LCA(a, b);
return sumWeight[a] + sumWeight[b] - 2 * sumWeight[lca];
}
void calc(long long u, long long p) {
sz[u] = 1;
for (pair<long long, long long> &x : g[u]) {
long long v, w; tie(v, w) = x;
if (blocked[v] || v == p) continue;
calc(v, u);
sz[u] += sz[v];
}
}
long long FindCentroid(long long u, long long p, long long SZ) {
for (pair<long long, long long> &x : g[u]) {
long long v, w; tie(v, w) = x;
if (blocked[v] || v == p) continue;
if (sz[v] > SZ) return FindCentroid(v, u, SZ);
}
return u;
}
void decompose(long long curNode, long long preCentroid) {
calc(curNode, 0);
long long c = FindCentroid(curNode, 0, sz[curNode] / 2);
par[c] = preCentroid;
blocked[c] = true;
for (pair<long long, long long> &x : g[c]) {
long long v, w; tie(v, w) = x;
if (blocked[v]) continue;
decompose(v, c);
}
}
void update(long long curNode) {
long long fixed = curNode;
while (curNode != 0) {
minimize(bestVal[curNode], dist(fixed, curNode));
curNode = up[curNode][0];
}
}
void reset(long long curNode) {
long long fixed = curNode;
while (curNode != 0) {
bestVal[curNode] = 1e15;
curNode = up[curNode][0];
}
}
long long query(long long curNode) {
long long fixed = curNode;
long long res = INF;
while (curNode != 0) {
minimize(res, bestVal[curNode] + dist(curNode, fixed));
curNode = up[curNode][0];
}
return res;
}
void Init(long long N, long long A[], long long B[], long long D[]) {
n = N;
FOR(i, 1, n - 1){
long long u = A[i - 1];
long long v = B[i - 1];
long long w = D[i - 1];
u++;
v++;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
preCalc(1, 0);
prepareLCA();
decompose(1, 0);
FOR(i, 1, n) bestVal[i] = 1e15;
}
long long Query(long long S, long long X[], long long T, long long Y[]) {
vector<long long> tmpNode;
FOR(i, 1, S) {
long long curNode = X[i - 1];
curNode++;
update(curNode);
tmpNode.push_back(curNode);
}
long long res = INF;
FOR(i, 1, T) {
long long curNode = Y[i - 1];
curNode++;
minimize(res, query(curNode));
}
for (long long &curNode : tmpNode) reset(curNode);
return res;
}
//void solve() {
// cin >> n >> q;
// FOR(i, 1, n - 1) {
// long long u, v, w; cin >> u >> v >> w;
// u++; v++;
// g[u].push_back({v, w});
// g[v].push_back({u, w});
// }
// preCalc(1, 0);
// prepareLCA();
// decompose(1, 0);
// FOR(i, 1, n) bestVal[i] = 1e15;
// FOR(node1, 1, n) FOR(node2, 1, n) {
// cerr << "test: " << node1 - 1 << ' ' << node2 - 1 << ' ' << dist(node1, node2) << '\n';
// }
// FOR(Nium, 1, q) {
// long long S, T; cin >> S >> T;
// vector<long long> tmpNode;
// FOR(i, 1, S) {
// long long curNode; cin >> curNode;
// curNode++;
// update(curNode);
// tmpNode.push_back(curNode);
// }
// long long res = INF;
// FOR(i, 1, T) {
// long long curNode; cin >> curNode;
// curNode++;
// minimize(res, query(curNode));
// }
// for (long long &curNode : tmpNode) reset(curNode);
// cout << res << '\n';
// }
//}
//
///++++++++++++++++++++++++++++++++++++++///
//
//#define task "test"
//int32_t main() {
// if (fopen(task".inp","r")) {
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr); cout.tie(nullptr);
// solve();
// bool M2;
// cerr << "++++++++++++++++++++++++++++\n";
// cerr << "Time: " << clock() << "ms" << '\n';
// cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << "MB" << '\n';
// cerr << "++++++++++++++++++++++++++++\n";
// return 0;
//}