#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<int, int> 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];
assert(deb + (1 << lg) <= fin+1);
assert(deb + (1 << lg) >= fin - (1<<lg) + 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();
cerr << "finished init" << endl;
}
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 |
Runtime error |
266 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
268 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
266 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |