#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define x first
#define y second
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)
const int N = 5e5 + 1;
const int lg = 20;
vector<pair<int, int>> g[N];
int p[N];
ll d[lg][N], dth[N];
int root = -1;
void tata(int v, int pa, ll cu, int death) {
d[death][v] = cu;
for(auto to : g[v]) {
if (to.x == pa || p[to.x] != -1) continue;
tata(to.x, v, cu + to.y, death);
}
}
int dfs(int v, int pa, int &c, int n) {
int sz = 1;
for(auto to : g[v]) {
if (to.x == pa || p[to.x] != -1) continue;
sz += dfs(to.x, v, c, n);
}
if (c == -1 && (sz * 2 >= n || pa == -1))
c = v;
return sz;
}
void dec(int v, int n) {
tata(v, -1, 0, dth[v]);
for(auto to : g[v]) {
if (p[to.x] == -1) {
int nx = -1;
dfs(to.x, -1, nx, n / 2);
p[nx] = v;
dth[nx] = dth[v] + 1;
dec(nx, n / 2);
}
}
}
int n;
const ll INF = 1e18;
ll used[N], f[2][N];
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n - 1; i++) {
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
fill(p, p + N, -1);
dfs(0, -1, root, n);
p[root] = root;
dec(root, N);
}
int timer = 0;
ll ans;
long long Query(int S, int X[], int T, int Y[]) {
timer++;
ans = INF;
for(int i : {0, 1}) {
for(int j = 0; j < (i == 0 ? S : T); j++) {
int x;
if (!i) x = X[j];
else x = Y[j];
ll val = x, e = dth[x];
while (1) {
if (used[x] != timer) {
used[x] = timer;
f[0][x] = INF;
f[1][x] = INF;
}
f[i][x] = min(f[i][x], d[e][val]);
chkmin(ans, f[0][x] + f[1][x]);
if (p[x] != x) {
x = p[x];
--e;
} else {
break;
}
}
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
12544 KB |
Output is correct |
2 |
Correct |
392 ms |
21112 KB |
Output is correct |
3 |
Correct |
506 ms |
21240 KB |
Output is correct |
4 |
Correct |
444 ms |
21240 KB |
Output is correct |
5 |
Correct |
445 ms |
21468 KB |
Output is correct |
6 |
Correct |
330 ms |
20600 KB |
Output is correct |
7 |
Correct |
447 ms |
21240 KB |
Output is correct |
8 |
Correct |
444 ms |
21192 KB |
Output is correct |
9 |
Correct |
442 ms |
21496 KB |
Output is correct |
10 |
Correct |
306 ms |
20728 KB |
Output is correct |
11 |
Correct |
437 ms |
21328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
12416 KB |
Output is correct |
2 |
Correct |
3077 ms |
135744 KB |
Output is correct |
3 |
Correct |
3980 ms |
138032 KB |
Output is correct |
4 |
Correct |
872 ms |
69804 KB |
Output is correct |
5 |
Correct |
4734 ms |
166584 KB |
Output is correct |
6 |
Correct |
4113 ms |
139552 KB |
Output is correct |
7 |
Correct |
1573 ms |
44508 KB |
Output is correct |
8 |
Correct |
523 ms |
32876 KB |
Output is correct |
9 |
Correct |
1802 ms |
48376 KB |
Output is correct |
10 |
Correct |
1627 ms |
45404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
12544 KB |
Output is correct |
2 |
Correct |
392 ms |
21112 KB |
Output is correct |
3 |
Correct |
506 ms |
21240 KB |
Output is correct |
4 |
Correct |
444 ms |
21240 KB |
Output is correct |
5 |
Correct |
445 ms |
21468 KB |
Output is correct |
6 |
Correct |
330 ms |
20600 KB |
Output is correct |
7 |
Correct |
447 ms |
21240 KB |
Output is correct |
8 |
Correct |
444 ms |
21192 KB |
Output is correct |
9 |
Correct |
442 ms |
21496 KB |
Output is correct |
10 |
Correct |
306 ms |
20728 KB |
Output is correct |
11 |
Correct |
437 ms |
21328 KB |
Output is correct |
12 |
Correct |
10 ms |
12416 KB |
Output is correct |
13 |
Correct |
3077 ms |
135744 KB |
Output is correct |
14 |
Correct |
3980 ms |
138032 KB |
Output is correct |
15 |
Correct |
872 ms |
69804 KB |
Output is correct |
16 |
Correct |
4734 ms |
166584 KB |
Output is correct |
17 |
Correct |
4113 ms |
139552 KB |
Output is correct |
18 |
Correct |
1573 ms |
44508 KB |
Output is correct |
19 |
Correct |
523 ms |
32876 KB |
Output is correct |
20 |
Correct |
1802 ms |
48376 KB |
Output is correct |
21 |
Correct |
1627 ms |
45404 KB |
Output is correct |
22 |
Correct |
3894 ms |
137208 KB |
Output is correct |
23 |
Correct |
4062 ms |
139500 KB |
Output is correct |
24 |
Correct |
5470 ms |
139828 KB |
Output is correct |
25 |
Correct |
5472 ms |
143336 KB |
Output is correct |
26 |
Correct |
5658 ms |
140112 KB |
Output is correct |
27 |
Correct |
6381 ms |
163368 KB |
Output is correct |
28 |
Correct |
1177 ms |
73768 KB |
Output is correct |
29 |
Correct |
5321 ms |
139608 KB |
Output is correct |
30 |
Correct |
5592 ms |
138840 KB |
Output is correct |
31 |
Correct |
5318 ms |
139644 KB |
Output is correct |
32 |
Correct |
1708 ms |
49400 KB |
Output is correct |
33 |
Correct |
525 ms |
33180 KB |
Output is correct |
34 |
Correct |
1280 ms |
42016 KB |
Output is correct |
35 |
Correct |
1284 ms |
41976 KB |
Output is correct |
36 |
Correct |
1603 ms |
42800 KB |
Output is correct |
37 |
Correct |
1564 ms |
42744 KB |
Output is correct |