#include "factories.h"
#include <algorithm>
#include <vector>
#define N 500001
#define NN 1048576
#define LL long long
#define INF 999999999999999999
#define max2(x,y) (x>y?x:y)
using namespace std;
int n, nn, t[N], tree_up[N][20], p[20];
int tree_lev[N], tree_e[N];
LL deep[N], seg[2][NN];
vector<pair<int, int> > r[N];
int dfs_lev, q_len, q[N*3];
LL min2(LL x, LL y) {
return x < y ? x : y;
}
void dfs(int x, int up, LL _deep, int _t) {
tree_lev[x] = ++dfs_lev;
deep[dfs_lev] = _deep, t[dfs_lev] = _t;
tree_up[dfs_lev][0] = tree_lev[up];
for (int i = 1; i < 20; i++)
tree_up[dfs_lev][i] = tree_up[tree_up[dfs_lev][i - 1]][i - 1];
for (auto i : r[x])
if (i.first != up) dfs(i.first, x, _deep + (LL)i.second, _t + 1);
tree_e[tree_lev[x]] = dfs_lev;
}
void Init(int _n, int *a, int *b, int *d) {
n = _n;
for (nn = 1; nn < n; nn *= 2);
for (int i = 1; i < nn * 2; i++) seg[0][i] = seg[1][i] = INF;
for (int i = 0; i < n - 1; i++) {
r[a[i] + 1].push_back({ b[i] + 1,d[i] });
r[b[i] + 1].push_back({ a[i] + 1,d[i] });
} dfs(1, 0, 0, 1);
p[0] = 1;
for (int i = 1; i < 20; i++) p[i] = p[i - 1] * 2;
}
int lca(int x, int y) {
for (int i = 19; i >= 0; i--)
if (t[x] - p[i] >= t[y]) x = tree_up[x][i];
for (int i = 19; i >= 0; i--)
if (t[y] - p[i] >= t[x]) y = tree_up[y][i];
for(int i=19; i>=0; i--)
if (tree_up[x][i] != tree_up[y][i])
x = tree_up[x][i], y = tree_up[y][i];
if (x != y) x = tree_up[x][0];
return x;
}
void Update(int x, int y) {
seg[x][y] = min2(seg[x][y * 2], seg[x][y * 2 + 1]);
if (y > 1) Update(x, y / 2);
}
LL get_seg(int lev, int l, int r, int x, int y, int seg_num) {
int mid = (l + r) / 2;
if (r < x || y < l) return INF;
if (x <= l && r <= y) return seg[seg_num][lev];
return min2(get_seg(lev * 2, l, mid, x, y, seg_num), get_seg(lev * 2 + 1, mid + 1, r, x, y, seg_num));
}
LL Query(int a_len, int a[], int b_len, int b[]) {
int temp;
LL out = INF;
q_len = 0;
for (int i = 0; i < a_len; i++) {
temp = tree_lev[a[i] + 1];
q[++q_len] = temp, seg[0][nn + temp - 1] = deep[temp];
Update(0, (nn + temp - 1) / 2);
}
for (int i = 0; i < b_len; i++) {
temp = tree_lev[b[i] + 1];
q[++q_len] = temp, seg[1][nn + temp - 1] = deep[temp];
Update(1, (nn + temp - 1) / 2);
}
sort(q + 1, q + q_len + 1), temp = q_len;
for (int i = 1; i < temp; i++) q[++q_len] = lca(q[i], q[i + 1]);
/* for (int i = 1; i <= q_len; i++) {
LL len1 = get_seg(1, 1, nn, q[i], tree_e[q[i]], 0);
LL len2 = get_seg(1, 1, nn, q[i], tree_e[q[i]], 1);
LL len3 = deep[q[i]];
out = min2(out, len1 + len2 - len3 * 2);
}*/
for (int i = 0; i < a_len; i++) {
temp = tree_lev[a[i] + 1];
seg[0][nn + temp - 1] = INF;
Update(0, (nn + temp - 1) / 2);
}
for (int i = 0; i < b_len; i++) {
temp = tree_lev[b[i] + 1];
seg[1][nn + temp - 1] = INF;
Update(1, (nn + temp - 1) / 2);
}
return out;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
106232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
106232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3463 ms |
124976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
