#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll inf = 1e18;
const int maxn = 5e5 + 100;
const int LOG = 20;
int n;
vector<pair<ll,int>> g[maxn];
int par[LOG+1][maxn];
int dep[maxn];
ll len[maxn];
void dfs(int at, int p) {
for (int j=1; j<LOG; j++) {
par[j][at] = par[j-1][par[j-1][at]];
}
for (auto ed: g[at]) {
ll wei = ed.first;
int to = ed.second;
if (to == p) continue;
dep[to] = 1+dep[at];
len[to] = len[at] + wei;
par[0][to] = at;
dfs(to, at);
}
}
int lca(int u, int v) {
if (dep[u]<dep[v]) swap(u, v);
int dx = dep[u]-dep[v];
for (int j=0; j<LOG; j++) {
if (dx>>j&1) {
u = par[j][u];
}
}
if (u == v) return u;
for (int j=LOG-1; j>=0; j--) {
if (par[j][u] != par[j][v]) {
u = par[j][u];
v = par[j][v];
}
}
return par[0][u];
}
ll dist(int u, int v) {
int mid = lca(u, v);
return len[u] + len[v] - 2ll*len[mid];
}
vector<int> ctree[maxn];
bool bad[maxn];
int siz[maxn];
int findCenter(int at) {
function<void(int,int)> dfs = [&](int at, int p) {
siz[at] = 1;
for (auto ed: g[at]) {
int to = ed.second;
if (!bad[to] && to != p) {
dfs(to, at);
siz[at] += siz[to];
}
}
};
dfs(at, -1);
int all = siz[at];
bool ok = true;
while (ok) {
ok = false;
for (auto ed: g[at]) {
int to = ed.second;
if (bad[to]) continue;
if (siz[to] > siz[at]) continue;
if (siz[to]*2 >= all) {
at = to;
ok = true;
break;
}
}
}
return at;
}
int build(int at) {
at = findCenter(at);
bad[at] = true;
for (auto ed: g[at]) {
int to = ed.second;
if (!bad[to]) {
int nc = build(to);
ctree[at].push_back(nc);
ctree[nc].push_back(at);
}
}
return at;
}
int cpar[maxn];
void cdfs(int at, int p) {
for (int to: ctree[at]) {
if (to == p) continue;
cpar[to] = at;
cdfs(to, at);
}
}
ll nearest[maxn];
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];
ll d = D[i];
g[u].push_back({d,v});
g[v].push_back({d,u});
}
dfs(0, -1);
int root = build(0);
cpar[root] = -1;
cdfs(root, -1);
for (int i=0; i<n+10; i++) {
nearest[i] = inf;
}
}
long long Query(int S, int X[], int T, int Y[]) {
ll res = inf;
vector<int> v;
for (int i=0; i<S; i++) {
int node = X[i];
int at = node;
while (~at) {
v.push_back(at);
nearest[at] = min(nearest[at], dist(node, at));
at = cpar[at];
}
}
for (int i=0; i<T; i++) {
int node = Y[i];
int at = node;
while (~at) {
v.push_back(at);
ll cur = nearest[at] + dist(node, at);
res = min(res, cur);
at = cpar[at];
}
}
while (v.size()) {
nearest[v.back()] = inf;
v.pop_back();
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
24440 KB |
Output is correct |
2 |
Correct |
1405 ms |
33332 KB |
Output is correct |
3 |
Correct |
2287 ms |
42684 KB |
Output is correct |
4 |
Correct |
2263 ms |
42944 KB |
Output is correct |
5 |
Correct |
2440 ms |
43428 KB |
Output is correct |
6 |
Correct |
523 ms |
42616 KB |
Output is correct |
7 |
Correct |
2280 ms |
42616 KB |
Output is correct |
8 |
Correct |
2401 ms |
43288 KB |
Output is correct |
9 |
Correct |
2438 ms |
43468 KB |
Output is correct |
10 |
Correct |
529 ms |
42636 KB |
Output is correct |
11 |
Correct |
2231 ms |
42488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
24192 KB |
Output is correct |
2 |
Correct |
6595 ms |
132016 KB |
Output is correct |
3 |
Execution timed out |
8087 ms |
134536 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
24440 KB |
Output is correct |
2 |
Correct |
1405 ms |
33332 KB |
Output is correct |
3 |
Correct |
2287 ms |
42684 KB |
Output is correct |
4 |
Correct |
2263 ms |
42944 KB |
Output is correct |
5 |
Correct |
2440 ms |
43428 KB |
Output is correct |
6 |
Correct |
523 ms |
42616 KB |
Output is correct |
7 |
Correct |
2280 ms |
42616 KB |
Output is correct |
8 |
Correct |
2401 ms |
43288 KB |
Output is correct |
9 |
Correct |
2438 ms |
43468 KB |
Output is correct |
10 |
Correct |
529 ms |
42636 KB |
Output is correct |
11 |
Correct |
2231 ms |
42488 KB |
Output is correct |
12 |
Correct |
24 ms |
24192 KB |
Output is correct |
13 |
Correct |
6595 ms |
132016 KB |
Output is correct |
14 |
Execution timed out |
8087 ms |
134536 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |