#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
const int MAXN = 5e5 + 5;
const int LOGN = 20;
const ll INF = 1e17;
vector<int> tree[MAXN];
vector<pair<int, int> > gr[MAXN];
//int par[MAXN][LOGN], lvl[MAXN];
//ll dist[MAXN];
int lvl[MAXN];
ll dist[MAXN][LOGN];
//unordered_map<int, ll> dist[MAXN];
bool mark[MAXN];
int sz[MAXN], cpar[MAXN], root;
ll ans[MAXN];
//int visit[MAXN];
/*
void init(int u) {
for (int j = 1; j < LOGN; j++)
if (par[u][j - 1] != -1)
par[u][j] = par[par[u][j - 1]][j - 1];
for (auto v : gr[u])
if (v.fi != par[u][0]) {
dist[v.fi] = dist[u] + v.se;
par[v.fi][0] = u;
lvl[v.fi] = lvl[u] + 1;
init(v.fi);
}
}
*/
void dfs(int u, int p, int dep) {
sz[u] = 1;
for (auto v : gr[u])
if (v.fi != p && !mark[v.fi]) {
if (dep != -1)
dist[v.fi][dep] = dist[u][dep] + v.se;
//dist[v.fi][who] = dist[u][who] + v.se;
dfs(v.fi, u, dep);
sz[u] += sz[v.fi];
}
}
void proc(int u, int p, int dep) {
ll w = dist[u][dep];
mark[u] = true;
for (auto v : gr[u])
if (v.fi != p && !mark[v.fi]) {
dist[v.fi][dep] = w + v.se;
proc(v.fi, u, dep);
}
}
/*
void init(int u) {
mark[u] = false;
//if (del) lvl[u] = -1;
for (auto v : tree[u]) {
//if (!del) lvl[v] = lvl[u] + 1;
init(v);
}
}
*/
int decompose(int u, int p, const int n, int dep) {
int mx = -1, big = -1;
for (auto v : gr[u])
if (v.fi != p && !mark[v.fi] && sz[v.fi] > mx)
mx = sz[v.fi], big = v.fi;
//printf("i am at %d and big child is %d\n", u, big);
if (2 * mx <= n) {
mark[u] = true;
lvl[u] = dep;
//printf("START OF VISIT OF %d\n", u);
for (auto v : gr[u])
if (!mark[v.fi]) {
//dist[v.fi][u] = v.se;
dist[v.fi][lvl[u]] = v.se;
dfs(v.fi, u, lvl[u]);
int cent = decompose(v.fi, u, sz[v.fi], dep + 1);
cpar[cent] = u;
tree[u].pb(cent);
//lvl[cent] = 1;
//init(cent, false);
//init(cent);
//value++;
//dist[v.fi][lvl[u]] = v.se;
//proc(v.fi, u, lvl[u]);
//init(cent, true);
}
//printf("END OF VISIT OF %d\n", u);
return u;
} else {
return decompose(big, u, n, dep);
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
gr[A[i]].pb(mp(B[i], D[i]));
gr[B[i]].pb(mp(A[i], D[i]));
}
/*for (int i = 0; i < N; i++) {
dist[i].reserve(LOGN);
dist[i][i] = 0;
}*/
//memset(par, -1, sizeof par);
//init(0);
memset(cpar, -1, sizeof cpar);
dfs(0, -1, -1);
//memset(lvl, -1, sizeof lvl);
//memset(dist, -1, sizeof dist);
root = decompose(0, -1, sz[0], 0);
fill(ans, ans + N + 1, INF);
/*init(root);
for (int i = 0; i < N; i++)
proc(i, i, cpar[i]);*/
/*printf("centroid is %d\n", root);
for (int u = 0; u < N; u++)
printf("cpar[%d] = %d\n", u, cpar[u]);*/
}
/*
unordered_map<int, int> memo[MAXN];
int LCA(int u, int v) {
if (lvl[u] > lvl[v]) swap(u, v);
if (memo[u].count(v))
return memo[u][v];
int &ret = memo[u][v];
for (int j = LOGN - 1; j >= 0; j--)
if (lvl[u] + (1 << j) <= lvl[v])
v = par[v][j];
if (u == v) return ret = u;
for (int j = LOGN - 1; j >= 0; j--)
if (par[u][j] != -1 && par[u][j] != par[v][j])
u = par[u][j], v = par[v][j];
return ret = par[u][0];
}
ll far(int u, int v) {
int l = LCA(u, v);
return dist[u] + dist[v] - dist[l] * 2LL;
}
*/
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
int u = X[i], c = lvl[X[i]];
while (u != -1) {
ans[u] = min(ans[u], dist[X[i]][c--]);
u = cpar[u];
}
}
ll res = INF;
for (int i = 0; i < T; i++) {
int u = Y[i], c = lvl[Y[i]];
while (u != -1) {
res = min(res, dist[Y[i]][c--] + ans[u]);
u = cpar[u];
}
}
for (int i = 0; i < S; i++) {
int u = X[i];
while (u != -1) {
ans[u] = INF;
u = cpar[u];
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
136108 KB |
Output is correct |
| 2 |
Correct |
429 ms |
136372 KB |
Output is correct |
| 3 |
Correct |
476 ms |
136372 KB |
Output is correct |
| 4 |
Correct |
423 ms |
136372 KB |
Output is correct |
| 5 |
Correct |
446 ms |
136668 KB |
Output is correct |
| 6 |
Correct |
366 ms |
136408 KB |
Output is correct |
| 7 |
Correct |
436 ms |
136372 KB |
Output is correct |
| 8 |
Correct |
489 ms |
136372 KB |
Output is correct |
| 9 |
Correct |
479 ms |
136660 KB |
Output is correct |
| 10 |
Correct |
306 ms |
136408 KB |
Output is correct |
| 11 |
Correct |
399 ms |
136372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
136108 KB |
Output is correct |
| 2 |
Correct |
1859 ms |
161848 KB |
Output is correct |
| 3 |
Correct |
3019 ms |
166920 KB |
Output is correct |
| 4 |
Correct |
1216 ms |
160004 KB |
Output is correct |
| 5 |
Correct |
4189 ms |
200152 KB |
Output is correct |
| 6 |
Correct |
2989 ms |
166276 KB |
Output is correct |
| 7 |
Correct |
1136 ms |
142136 KB |
Output is correct |
| 8 |
Correct |
586 ms |
141360 KB |
Output is correct |
| 9 |
Correct |
1293 ms |
146008 KB |
Output is correct |
| 10 |
Correct |
1066 ms |
141988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2659 ms |
161848 KB |
Output is correct |
| 2 |
Correct |
2713 ms |
161848 KB |
Output is correct |
| 3 |
Correct |
3433 ms |
165444 KB |
Output is correct |
| 4 |
Correct |
3843 ms |
166300 KB |
Output is correct |
| 5 |
Correct |
3959 ms |
166100 KB |
Output is correct |
| 6 |
Correct |
4609 ms |
191484 KB |
Output is correct |
| 7 |
Correct |
1453 ms |
160004 KB |
Output is correct |
| 8 |
Correct |
3233 ms |
165548 KB |
Output is correct |
| 9 |
Correct |
3496 ms |
164756 KB |
Output is correct |
| 10 |
Correct |
3233 ms |
165608 KB |
Output is correct |
| 11 |
Correct |
1289 ms |
146728 KB |
Output is correct |
| 12 |
Correct |
453 ms |
141360 KB |
Output is correct |
| 13 |
Correct |
813 ms |
141256 KB |
Output is correct |
| 14 |
Correct |
819 ms |
141256 KB |
Output is correct |
| 15 |
Correct |
1029 ms |
142000 KB |
Output is correct |
| 16 |
Correct |
1049 ms |
141980 KB |
Output is correct |
