#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
#ifndef mlocal
#include "factories.h"
#endif
class SparseTable {
vector<vector<array<int, 2>>> st;
int n;
void buildTable(vector<array<int, 2>> &raw) {
int k = __lg(n)+1;
st.resize(n, vector<array<int, 2>> (k));
for_(i, 0, n) st[i][0] = raw[i];
for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1)
st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]);
}
public:
void build(vector<array<int, 2>> &nums) {
n = nums.size();
buildTable(nums);
}
int mn(int l, int r) {
int p = __lg(r-l+1);
return min(st[l][p], st[r - (1<<p) + 1][p])[1];
}
};
int n;
vector<vector<array<ll, 2>>> adjList;
vi removed, subtreeSize, centroid, tin, depth;
vector<ll> rootDist, whiteDist;
vector<vector<ll>> centroidDist;
vector<array<int, 2>> tour;
SparseTable st;
const ll INF = 1e15;
int dfs(int p, int parent) {
int s = 1;
tin[p] = tour.size();
tour.push_back({depth[p], p});
for (auto i: adjList[p]) if (i[0] != parent) {
rootDist[i[0]] = rootDist[p]+i[1];
depth[i[0]] = depth[p]+1;
s += dfs(i[0], p);
tour.push_back({depth[p], p});
}
subtreeSize[p] = s;
return s;
}
int lca(int u, int v) {
return st.mn(min(tin[u], tin[v]), max(tin[u], tin[v]));
}
ll dist(int u, int v) {
int lc = lca(u, v);
return rootDist[u] + rootDist[v] - 2*rootDist[lc];
}
void noteCentroidDist(int p, int parent) {
ll d = centroidDist[p].back();
for (auto i: adjList[p]) if (!removed[i[0]] and i[0] != parent) {
centroidDist[i[0]].push_back(d+i[1]);
noteCentroidDist(i[0], p);
}
}
void decompose(int p, int c) {
int invalidChild = -1, sizeLimit = (subtreeSize[p] >> 1);
for (auto i: adjList[p]) if (!removed[i[0]] and subtreeSize[i[0]] > sizeLimit) {
invalidChild = i[0];
break;
}
if (invalidChild != -1) {
subtreeSize[p] -= subtreeSize[invalidChild];
subtreeSize[invalidChild] += subtreeSize[p];
return decompose(invalidChild, c);
}
removed[p] = true;
centroid[p] = c;
centroidDist[p].push_back(0);
noteCentroidDist(p, p);
for (auto i: adjList[p]) if (!removed[i[0]]) {
centroid[i[0]] = p;
decompose(i[0], p);
}
}
vi updated;
int pt = 0;
void update(int p) {
int v = p, cpt = (int) centroidDist[p].size() - 1;
while (v != -1) {
ll d = centroidDist[p][cpt--];
whiteDist[v] = min(whiteDist[v], d);
updated[pt++] = v;
v = centroid[v];
}
}
ll ans(int p) {
ll val = INF;
int v = p, cpt = (int) centroidDist[p].size() - 1;
while (v != -1) {
val = min(val, whiteDist[v] + centroidDist[p][cpt--]);
v = centroid[v];
}
return (val == 1e9 ? -1 : val);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
adjList.resize(n); subtreeSize.resize(n); removed.resize(n); centroid.resize(n, -1); depth.resize(n); tin.resize(n); rootDist.resize(n); whiteDist.resize(n, INF); updated.resize(10*n); centroidDist.resize(n);
for_(i, 0, n-1) {
int a = A[i], b = B[i]; ll w = D[i];
adjList[a].push_back({b, w});
adjList[b].push_back({a, w});
}
dfs(0, 0);
decompose(0, -1);
st.build(tour);
}
ll Query(int S, int X[], int T, int Y[]) {
pt = 0;
for_(i, 0, S) update(X[i]);
ll val = INF;
for_(i, 0, T) val = min(val, ans(Y[i]));
for_(i, 0, pt) whiteDist[updated[i]] = INF;
return val;
}
#ifdef mlocal
int main() {
freopen("test.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, q;
cin >> N >> q;
int A[100], B[100], D[100];
for_(i, 0, N - 1) {
int a, b, w;
cin >> a >> b >> w;
A[i] = a;
B[i] = b;
D[i] = w;
}
Init(N, A, B, D);
int X[100], Y[100];
while (q--) {
int S, T;
cin >> S >> T;
for_(i, 0, S) cin >> X[i];
for_(i, 0, T) cin >> Y[i];
cout << Query(S, X, T, Y) << endl;
}
return 0;
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
1004 KB |
Output is correct |
2 |
Correct |
368 ms |
20908 KB |
Output is correct |
3 |
Correct |
407 ms |
20972 KB |
Output is correct |
4 |
Correct |
409 ms |
21228 KB |
Output is correct |
5 |
Correct |
433 ms |
21484 KB |
Output is correct |
6 |
Correct |
300 ms |
20460 KB |
Output is correct |
7 |
Correct |
404 ms |
21248 KB |
Output is correct |
8 |
Correct |
428 ms |
21024 KB |
Output is correct |
9 |
Correct |
427 ms |
21484 KB |
Output is correct |
10 |
Correct |
282 ms |
20460 KB |
Output is correct |
11 |
Correct |
408 ms |
20988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
748 KB |
Output is correct |
2 |
Correct |
3179 ms |
371188 KB |
Output is correct |
3 |
Correct |
4019 ms |
413400 KB |
Output is correct |
4 |
Correct |
1561 ms |
334956 KB |
Output is correct |
5 |
Correct |
4918 ms |
496388 KB |
Output is correct |
6 |
Correct |
4001 ms |
428688 KB |
Output is correct |
7 |
Correct |
1209 ms |
95120 KB |
Output is correct |
8 |
Correct |
596 ms |
83292 KB |
Output is correct |
9 |
Correct |
1389 ms |
105564 KB |
Output is correct |
10 |
Correct |
1296 ms |
96476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
1004 KB |
Output is correct |
2 |
Correct |
368 ms |
20908 KB |
Output is correct |
3 |
Correct |
407 ms |
20972 KB |
Output is correct |
4 |
Correct |
409 ms |
21228 KB |
Output is correct |
5 |
Correct |
433 ms |
21484 KB |
Output is correct |
6 |
Correct |
300 ms |
20460 KB |
Output is correct |
7 |
Correct |
404 ms |
21248 KB |
Output is correct |
8 |
Correct |
428 ms |
21024 KB |
Output is correct |
9 |
Correct |
427 ms |
21484 KB |
Output is correct |
10 |
Correct |
282 ms |
20460 KB |
Output is correct |
11 |
Correct |
408 ms |
20988 KB |
Output is correct |
12 |
Correct |
3 ms |
748 KB |
Output is correct |
13 |
Correct |
3179 ms |
371188 KB |
Output is correct |
14 |
Correct |
4019 ms |
413400 KB |
Output is correct |
15 |
Correct |
1561 ms |
334956 KB |
Output is correct |
16 |
Correct |
4918 ms |
496388 KB |
Output is correct |
17 |
Correct |
4001 ms |
428688 KB |
Output is correct |
18 |
Correct |
1209 ms |
95120 KB |
Output is correct |
19 |
Correct |
596 ms |
83292 KB |
Output is correct |
20 |
Correct |
1389 ms |
105564 KB |
Output is correct |
21 |
Correct |
1296 ms |
96476 KB |
Output is correct |
22 |
Correct |
3362 ms |
376740 KB |
Output is correct |
23 |
Correct |
3446 ms |
380132 KB |
Output is correct |
24 |
Correct |
4425 ms |
416392 KB |
Output is correct |
25 |
Correct |
4526 ms |
420528 KB |
Output is correct |
26 |
Correct |
4468 ms |
417140 KB |
Output is correct |
27 |
Correct |
5433 ms |
477344 KB |
Output is correct |
28 |
Correct |
1735 ms |
326352 KB |
Output is correct |
29 |
Correct |
4456 ms |
416296 KB |
Output is correct |
30 |
Correct |
4474 ms |
415240 KB |
Output is correct |
31 |
Correct |
4431 ms |
416360 KB |
Output is correct |
32 |
Correct |
1364 ms |
106588 KB |
Output is correct |
33 |
Correct |
597 ms |
83932 KB |
Output is correct |
34 |
Correct |
996 ms |
89824 KB |
Output is correct |
35 |
Correct |
1073 ms |
90144 KB |
Output is correct |
36 |
Correct |
1230 ms |
93660 KB |
Output is correct |
37 |
Correct |
1258 ms |
93432 KB |
Output is correct |