#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;
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]];
}
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();
cerr << "finished init" << endl;
}
vector<int> potentielsLca;
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 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]));
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
33644 KB |
Output is correct |
2 |
Correct |
1363 ms |
43520 KB |
Output is correct |
3 |
Correct |
1568 ms |
43596 KB |
Output is correct |
4 |
Correct |
1458 ms |
43840 KB |
Output is correct |
5 |
Correct |
1505 ms |
43884 KB |
Output is correct |
6 |
Correct |
1341 ms |
43500 KB |
Output is correct |
7 |
Correct |
1552 ms |
43548 KB |
Output is correct |
8 |
Correct |
1466 ms |
43628 KB |
Output is correct |
9 |
Correct |
1508 ms |
43756 KB |
Output is correct |
10 |
Correct |
1355 ms |
43628 KB |
Output is correct |
11 |
Correct |
1555 ms |
43628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
33516 KB |
Output is correct |
2 |
Correct |
4153 ms |
255792 KB |
Output is correct |
3 |
Correct |
5153 ms |
258068 KB |
Output is correct |
4 |
Correct |
3865 ms |
253512 KB |
Output is correct |
5 |
Correct |
5134 ms |
276972 KB |
Output is correct |
6 |
Correct |
5376 ms |
259464 KB |
Output is correct |
7 |
Correct |
7209 ms |
86276 KB |
Output is correct |
8 |
Correct |
5409 ms |
86524 KB |
Output is correct |
9 |
Correct |
6822 ms |
90084 KB |
Output is correct |
10 |
Correct |
7314 ms |
87948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
33644 KB |
Output is correct |
2 |
Correct |
1363 ms |
43520 KB |
Output is correct |
3 |
Correct |
1568 ms |
43596 KB |
Output is correct |
4 |
Correct |
1458 ms |
43840 KB |
Output is correct |
5 |
Correct |
1505 ms |
43884 KB |
Output is correct |
6 |
Correct |
1341 ms |
43500 KB |
Output is correct |
7 |
Correct |
1552 ms |
43548 KB |
Output is correct |
8 |
Correct |
1466 ms |
43628 KB |
Output is correct |
9 |
Correct |
1508 ms |
43756 KB |
Output is correct |
10 |
Correct |
1355 ms |
43628 KB |
Output is correct |
11 |
Correct |
1555 ms |
43628 KB |
Output is correct |
12 |
Correct |
23 ms |
33516 KB |
Output is correct |
13 |
Correct |
4153 ms |
255792 KB |
Output is correct |
14 |
Correct |
5153 ms |
258068 KB |
Output is correct |
15 |
Correct |
3865 ms |
253512 KB |
Output is correct |
16 |
Correct |
5134 ms |
276972 KB |
Output is correct |
17 |
Correct |
5376 ms |
259464 KB |
Output is correct |
18 |
Correct |
7209 ms |
86276 KB |
Output is correct |
19 |
Correct |
5409 ms |
86524 KB |
Output is correct |
20 |
Correct |
6822 ms |
90084 KB |
Output is correct |
21 |
Correct |
7314 ms |
87948 KB |
Output is correct |
22 |
Correct |
7581 ms |
259756 KB |
Output is correct |
23 |
Correct |
7523 ms |
261636 KB |
Output is correct |
24 |
Correct |
7753 ms |
263300 KB |
Output is correct |
25 |
Correct |
7813 ms |
266012 KB |
Output is correct |
26 |
Execution timed out |
8090 ms |
284268 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |