#include "factories.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<pair<int, int>>> g;
int nbSommets;
vector<int> tempsDeb, tempsFin;
vector<int> depthWeight, depth;
vector<int> eulerTour;
vector<int> posEuler;
int temps;
const int nbFeuilles = 1 << 20;
const int INF = 1e18;
struct Segtree
{
int seg[2 * nbFeuilles];
Segtree()
{
for (int i(0); i < 2 * nbFeuilles; ++i)
seg[i] = INF;
}
void update(int pos, int val)
{
pos += nbFeuilles;
seg[pos] = val;
while (pos > 1)
{
pos /= 2;
seg[pos] = min(seg[2*pos], seg[2*pos+1]);
}
}
int query(int deb, int fin)
{
deb += nbFeuilles, fin += nbFeuilles;
int ret = INF;
while (deb < fin)
{
if (deb % 2)
ret = min(ret, seg[deb]);
deb = (deb + 1)/2;
if (fin % 2 == 0)
ret = min(ret, seg[fin]);
fin = (fin - 1) / 2;
}
if (deb == fin)
ret = min(ret, seg[deb]);
return ret;
}
};
Segtree seg1, seg2;
const int MAXP = 21;
struct Sparse
{
pair<signed, signed> sparse[MAXP][1 << MAXP];
int log2[1 << MAXP];
void build()
{
log2[1] = 0;
for (int i(2); i < (1 << MAXP); ++i)
log2[i] = 1 + log2[i/2];
for (int i(0); i < (int)eulerTour.size(); ++i)
sparse[0][i] = make_pair(depth[eulerTour[i]], eulerTour[i]);
for (int p(1); p < MAXP; ++p)
for (int i(0); i < (int)eulerTour.size(); ++i)
sparse[p][i] = min(sparse[p-1][i],
sparse[p-1][min((int)eulerTour.size()-1, i + (1 << (p-1)))]);
}
int getMin(int deb, int fin)
{
if (deb > fin) swap(deb, fin);
int lg = log2[fin-deb+1];
return min(sparse[lg][deb], sparse[lg][fin - (1<<lg)+1]).second;
}
};
Sparse sparse;
void dfs(int u, int p=0)
{
tempsDeb[u] = temps++;
posEuler[u] = (int)eulerTour.size();
eulerTour.push_back(u);
for (auto [v,w] : g[u])
if (v != p)
{
depth[v] = depth[u] + 1;
depthWeight[v] = depthWeight[u] + w;
dfs(v, u);
eulerTour.push_back(u);
}
tempsFin[u] = temps++;
}
int calcLca(int u, int v)
{
return sparse.getMin(posEuler[u], posEuler[v]);
}
void Init(signed N, signed A[], signed B[], signed D[])
{
nbSommets = N;
g.resize(nbSommets);
tempsDeb.resize(nbSommets);
tempsFin.resize(nbSommets);
depth.resize(nbSommets);
depthWeight.resize(nbSommets);
posEuler.resize(nbSommets);
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]);
}
temps = 0;
dfs(0);
sparse.build();
}
vector<int> potentielsLca;
vector<int> sommetsRequete;
int Query(signed S, signed X[], signed T, signed Y[]) {
for (int i(0); i < S; ++i)
sommetsRequete.push_back(X[i]);
for (int i(0); i < T; ++i)
sommetsRequete.push_back(Y[i]);
sort(sommetsRequete.begin(), sommetsRequete.end(),
[&](int u, int v)
{
return tempsDeb[u]< tempsDeb[v];
});
potentielsLca.reserve((int)sommetsRequete.size() - 1);
for (int i(1); i < (int)sommetsRequete.size(); ++i)
potentielsLca.push_back(calcLca(sommetsRequete[i-1], sommetsRequete[i]));
sommetsRequete.clear();
int ret = INF;
for (int i(0); i < S; ++i)
seg1.update(tempsDeb[X[i]], depthWeight[X[i]]);
for (int i(0); i < T; ++i)
seg2.update(tempsDeb[Y[i]], depthWeight[Y[i]]);
for (auto lca : potentielsLca)
{
ret = min(ret, seg1.query(tempsDeb[lca], tempsFin[lca])
+ seg2.query(tempsDeb[lca], tempsFin[lca])
- 2 * depthWeight[lca]);
}
potentielsLca.clear();
for (int i(0); i < T; ++i)
seg2.update(tempsDeb[Y[i]], INF);
for (int i(0); i < S; ++i)
seg1.update(tempsDeb[X[i]], INF);
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
228 ms |
395116 KB |
Output is correct |
2 |
Correct |
1020 ms |
404180 KB |
Output is correct |
3 |
Correct |
1130 ms |
404076 KB |
Output is correct |
4 |
Correct |
1098 ms |
404204 KB |
Output is correct |
5 |
Correct |
1154 ms |
404460 KB |
Output is correct |
6 |
Correct |
979 ms |
404332 KB |
Output is correct |
7 |
Correct |
1132 ms |
404120 KB |
Output is correct |
8 |
Correct |
1109 ms |
404056 KB |
Output is correct |
9 |
Correct |
1160 ms |
404504 KB |
Output is correct |
10 |
Correct |
1008 ms |
404076 KB |
Output is correct |
11 |
Correct |
1138 ms |
404204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
212 ms |
394476 KB |
Output is correct |
2 |
Correct |
1858 ms |
472176 KB |
Output is correct |
3 |
Correct |
2236 ms |
476632 KB |
Output is correct |
4 |
Correct |
1565 ms |
469820 KB |
Output is correct |
5 |
Correct |
2310 ms |
499976 KB |
Output is correct |
6 |
Correct |
2325 ms |
476664 KB |
Output is correct |
7 |
Correct |
2371 ms |
419588 KB |
Output is correct |
8 |
Correct |
1617 ms |
419524 KB |
Output is correct |
9 |
Correct |
2450 ms |
423516 KB |
Output is correct |
10 |
Correct |
2324 ms |
421068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
228 ms |
395116 KB |
Output is correct |
2 |
Correct |
1020 ms |
404180 KB |
Output is correct |
3 |
Correct |
1130 ms |
404076 KB |
Output is correct |
4 |
Correct |
1098 ms |
404204 KB |
Output is correct |
5 |
Correct |
1154 ms |
404460 KB |
Output is correct |
6 |
Correct |
979 ms |
404332 KB |
Output is correct |
7 |
Correct |
1132 ms |
404120 KB |
Output is correct |
8 |
Correct |
1109 ms |
404056 KB |
Output is correct |
9 |
Correct |
1160 ms |
404504 KB |
Output is correct |
10 |
Correct |
1008 ms |
404076 KB |
Output is correct |
11 |
Correct |
1138 ms |
404204 KB |
Output is correct |
12 |
Correct |
212 ms |
394476 KB |
Output is correct |
13 |
Correct |
1858 ms |
472176 KB |
Output is correct |
14 |
Correct |
2236 ms |
476632 KB |
Output is correct |
15 |
Correct |
1565 ms |
469820 KB |
Output is correct |
16 |
Correct |
2310 ms |
499976 KB |
Output is correct |
17 |
Correct |
2325 ms |
476664 KB |
Output is correct |
18 |
Correct |
2371 ms |
419588 KB |
Output is correct |
19 |
Correct |
1617 ms |
419524 KB |
Output is correct |
20 |
Correct |
2450 ms |
423516 KB |
Output is correct |
21 |
Correct |
2324 ms |
421068 KB |
Output is correct |
22 |
Correct |
3199 ms |
475776 KB |
Output is correct |
23 |
Correct |
2980 ms |
478408 KB |
Output is correct |
24 |
Correct |
3422 ms |
479908 KB |
Output is correct |
25 |
Correct |
3382 ms |
482740 KB |
Output is correct |
26 |
Correct |
3727 ms |
477384 KB |
Output is correct |
27 |
Correct |
3330 ms |
524288 KB |
Output is correct |
28 |
Correct |
2602 ms |
500968 KB |
Output is correct |
29 |
Correct |
3584 ms |
501464 KB |
Output is correct |
30 |
Correct |
3610 ms |
500932 KB |
Output is correct |
31 |
Correct |
3647 ms |
501320 KB |
Output is correct |
32 |
Correct |
1820 ms |
439480 KB |
Output is correct |
33 |
Correct |
1543 ms |
434984 KB |
Output is correct |
34 |
Correct |
1942 ms |
430180 KB |
Output is correct |
35 |
Correct |
1873 ms |
430200 KB |
Output is correct |
36 |
Correct |
2213 ms |
431196 KB |
Output is correct |
37 |
Correct |
2209 ms |
431092 KB |
Output is correct |