#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define all(x) x.begin(), x.end()
vector<vector<pair<int, ll>>> graph;
vector<vector<int>> ctree;
int croot;
vector<vector<ll>> depth, subtree; // [level][v]
constexpr int L = 20;
int n;
void Init(int nn, int a[], int b[], int d[]) {
n = nn;
graph.resize(n);
ctree.resize(n);
depth.assign(L, vector<ll>(n));
subtree.assign(L, vector<ll>(n));
for (int i = 0; i < n-1; i++) {
graph[a[i]].emplace_back(b[i], d[i]);
graph[b[i]].emplace_back(a[i], d[i]);
}
vector<bool> vis(n);
vector<int> sz(n);
function<int(int, int, int, int)> calc = [&](int v, int p, int l, int c) {
if (v == p and l >= 0)
depth[l][v] = 0;
if (l > 0)
subtree[l-1][v] = c;
sz[v] = 1;
for (auto [ne, w] : graph[v])
if (!vis[ne] and ne != p) {
if (l >= 0)
depth[l][ne] = depth[l][v]+w;
sz[v] += calc(ne, v, l, c);
}
return sz[v];
};
function<int(int, int)> centroid = [&](int v, int l) {
int k = calc(v, v, -1, 0), c = v;
bool cont = true;
while (cont) {
cont = false;
for (auto [ne, w] : graph[c]) if (!vis[ne] and sz[ne] < sz[c] and 2*sz[ne] > k)
cont = true, c = ne;
}
calc(c, c, l, c);
vis[c] = true;
for (auto [ne, w] : graph[c]) {
if (!vis[ne])
ctree[c].push_back(centroid(ne, l+1));
}
return c;
};
croot = centroid(0, 0);
}
long long Query(int s, int x[], int t, int y[]) {
vector<vector<int>> a(n), b(n);
function<ll(int, int)> calc = [&](int v, int l) {
if (a[v].empty() or b[v].empty()) return LLONG_MAX;
/*cout << v << endl;
for (int e : a[v])
cout << " " << e;
cout << endl;
for (int e : b[v])
cout << " " << e;
cout << endl;*/
ll ax = LLONG_MAX, bx = LLONG_MAX;
for (int e : a[v])
ax = min(ax, depth[l][e]), a[subtree[l][e]].push_back(e);
for (int e : b[v])
bx = min(bx, depth[l][e]), b[subtree[l][e]].push_back(e);
ll res = ax+bx;
for (int ne : ctree[v])
res = min(res, calc(ne, l+1));
return res;
};
for (int i = 0; i < s; i++)
a[croot].push_back(x[i]);
for (int i = 0; i < t; i++)
b[croot].push_back(y[i]);
return calc(croot, 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1612 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1100 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1612 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
