| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1053108 | manhlinh1501 | 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>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 5e5 + 5;
const int LOGN = 20;
const i64 oo64 = 1e18;
using pli = pair<i64, int>;
int N, Q;
vector<pii> adj[MAXN];
int up[MAXN][LOGN];
int depth[MAXN];
i64 dist[MAXN];
void DFS(int u, int p = -1) {
for(auto [v, w] : adj[u]) {
if(v == p) continue;
dist[v] = dist[u] + w;
depth[v] = depth[u] + 1;
up[v][0] = u;
for(int i = 1; i < LOGN; i++)
up[v][i] = up[up[v][i - 1]][i - 1];
DFS(v, u);
}
}
int LCA(int u, int v) {
if(depth[u] != depth[v]) {
if(depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
for(int i = 0; (1 << i) <= k; i++) {
if(k >> i & 1)
u = up[u][i];
}
}
if(u == v) return u;
int b = 31 - __builtin_clz(depth[u] - depth[v]);
for(int i = b; i >= 0; i--) {
if(up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
void Init(int _N, int A[], int B[], int D[]) {
N = _N;
for(int i = 0; i < N - 1; i++) {
int u = A[i];
int v = B[i];
int w = D[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
DFS(0);
}
i64 get_dist(int u, int v) {
return dist[u] + dist[v] - 2 * dist[LCA(u, v)];
}
namespace subtask1 {
i64 Query(int S, int X[], int T, int Y[]) {
if(S < T) {
swap(X, Y);
swap(S, T);
}
vector<i64> dist(N, oo64);
priority_queue<pli, vector<pli>, greater<pli>> Q;
for(int i = 0; i < S; i++) {
int u = X[i];
dist[u] = 0;
Q.emplace(dist[u], u);
}
while(!Q.empty()) {
pli top = Q.top();
Q.pop();
int u = top.second;
if(top.first != dist[u]) continue;
for(pii _ : adj[u]) {
int v = _.first;
int w = _.second;
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
Q.emplace(dist[v], v);
}
}
}
i64 ans = oo64;
for(int i = 0; i < T; i++) {
int u = Y[i];
ans = min(ans, dist[u]);
}
return ans;
}
}
namespace subtask2 {
i64 Query(int S, int X[], int T, int Y[]) {
i64 ans = oo64;
for(int i = 0; i < S; i++) {
for(int j = 0; j < T; j++) {
int u = X[i];
int v = Y[i];
ans = min(ans, get_dist(u, v));
}
}
return ans;
}
}
i64 Query(int S, int X[], int T, int Y[]) {
return subtask2::Query(S, X, T, Y);
}
signed main() {
#define TASK "code"
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
for(int i = 1; i < N; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
return (0 ^ 0);
}