#include "factories.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXP = 20;
vector<vector<pair<int, int>>> g;
int nbSommets;
vector<int> tempsDeb, tempsFin;
vector<int> par[MAXP], parWeight[MAXP];
vector<int> depthWeight, depth;
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;
/*
* 1
* 2 3
* 4 5 6 7
*/
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;
void dfs(int u)
{
tempsDeb[u] = temps++;
for (auto [v,w] : g[u])
if (v != par[0][u])
{
par[0][v] = u;
parWeight[0][v] = w;
depth[v] = depth[u] + 1;
depthWeight[v] = depthWeight[u] + w;
dfs(v);
}
tempsFin[u] = temps++;
}
void initLca()
{
for (int p(1); p < MAXP; ++p)
for (int u(0); u < nbSommets; ++u)
{
par[p][u] = par[p-1][par[p-1][u]];
parWeight[p][u] = parWeight[p-1][par[p-1][u]] + parWeight[p-1][u];
}
}
int calcLca(int u, int v)
{
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int p(0); p < MAXP; ++p)
if ((1<<p) & diff)
u = par[p][u];
for (int p(MAXP-1); p >= 0; --p)
if (par[p][u] != par[p][v])
{
u = par[p][u];
v = par[p][v];
}
if (u != v)
return par[0][u];
return u;
}
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);
for (int p(0); p < MAXP; ++p)
par[p].resize(nbSommets), parWeight[p].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);
initLca();
//for (int i(0); i < nbSommets; ++i)
//cerr << i << ' ' << tempsDeb[i] << ' ' << tempsFin[i] << endl;
}
int Query(signed S, signed X[], signed T, signed Y[]) {
vector<int> sommetsRequete;
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 make_pair(tempsDeb[u], u) < make_pair(tempsDeb[v], v);
});
sort(sommetsRequete.begin(), sommetsRequete.end());
sommetsRequete.resize(unique(sommetsRequete.begin(), sommetsRequete.end())-sommetsRequete.begin());
vector<int> potentielsLca;
for (int i(1); i < (int)sommetsRequete.size(); ++i)
potentielsLca.push_back(calcLca(sommetsRequete[i-1], sommetsRequete[i]));
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]]);
//cerr << "nouvelles requete" << endl;
for (auto lca : potentielsLca)
{
//cerr << lca << ' ' << tempsDeb[lca] << ' ' << tempsFin[lca] << endl;
ret = min(ret, seg1.query(tempsDeb[lca], tempsFin[lca])
+ seg2.query(tempsDeb[lca], tempsFin[lca])
- 2 * depthWeight[lca]);
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
33900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
33516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
33900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
