#include "factories.h"
#include <vector>
//#include <iostream>
#include <algorithm>
#include <set>
#include <stack>
using namespace std;
const int NMAX = 500000;
const int LGMAX = 19;
const long long INF = 1e18;
vector<pair<int, int> > g[NMAX + 5];
long long dist[NMAX + 5];
int lvl[NMAX + 5];
int firstAp[NMAX + 2];
vector<int> rmq[LGMAX + 2];
int log2[2 * NMAX + 2];
void dfs(int node, int parent = -1) {
firstAp[node] = (int) rmq[0].size();
rmq[0].push_back(node);
for (auto it : g[node]) {
if (it.first != parent) {
lvl[it.first] = lvl[node] + 1;
dist[it.first] = dist[node] + it.second;
dfs(it.first, node);
rmq[0].push_back(node);
}
}
}
int GetMinLvl(int A, int B) {
if (lvl[A] < lvl[B]) {
return A;
}
return B;
}
void BuildRmq() {
log2[1] = 0;
for (int i = 2; i <= 2 * NMAX; i++) {
log2[i] = log2[i / 2] + 1;
}
for (int i = 1; i <= LGMAX; i++) {
if ((1 << i) > (int) rmq[0].size()) {
break;
} else {
for (int j = 0; j < (int) rmq[0].size(); j++) {
if (j + (1 << i) > (int) rmq[0].size()) {
break;
} else {
rmq[i].push_back(GetMinLvl(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
}
}
}
}
}
int LCA(int A, int B) {
A = firstAp[A];
B = firstAp[B];
if (A > B)
swap(A, B);
int k = log2[B - A + 1];
return GetMinLvl(rmq[k][A], rmq[k][B - (1 << k) + 1]);
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 1; i < N; i++) {
g[A[i - 1]].push_back({B[i - 1], D[i - 1]});
g[B[i - 1]].push_back({A[i - 1], D[i - 1]});
}
dfs(0);
BuildRmq();
}
vector<pair<int, long long>> g2[NMAX + 2];
long long dp1[NMAX + 2], dp2[NMAX + 2];
void computeDp1(int node, int parent = -1) {
for (auto it : g2[node]) {
if (it.first != parent) {
computeDp1(it.first, node);
dp1[node] = min(dp1[node], it.second + dp1[it.first]);
}
}
}
void computeDp2(int node, int parent = -1) {
dp2[node] = min(dp1[node], dp2[node]);
for (auto it : g2[node]) {
if (it.first != parent) {
dp2[it.first] = min(dp2[it.first], it.second + dp2[node]);
computeDp2(it.first, node);
}
}
}
bool isAncestor(int A, int B) {
return (A == LCA(A, B));
}
long long GetDist(int A, int B) {
return dist[A] + dist[B] - 2 * dist[LCA(A, B)];
}
long long Solve(vector<int> &base, vector<int> &red, vector<int> &blue) {
for (auto it : base) {
g2[it].clear();
dp1[it] = dp2[it] = INF;
}
for (auto it : red) {
dp1[it] = 0;
}
stack<int> st;
for (auto vert : base) {
while (!st.empty() && isAncestor(st.top(), vert) == false) {
st.pop();
}
if (!st.empty()) {
long long dist = GetDist(st.top(), vert);
g2[st.top()].push_back({vert, dist});
g2[vert].push_back({st.top(), dist});
}
st.push(vert);
}
computeDp1(base[0]);
computeDp2(base[0]);
long long ans = INF;
for (auto it : blue) {
ans = min(ans, dp2[it]);
}
return ans;
}
inline bool cmp(const int A, const int B) {
return firstAp[A] < firstAp[B];
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> base;
for (int i = 0; i < S; i++)
base.push_back(X[i]);
for (int i = 0; i < T; i++)
base.push_back(Y[i]);
sort(base.begin(), base.end(), cmp);
vector<int> aux = base;
for (int i = 1; i < (int) base.size(); i++)
aux.push_back(LCA(base[i - 1], base[i]));
set<int> vertices;
for (auto it : aux)
vertices.insert(it);
base.clear();
for (auto it : vertices)
base.push_back(it);
sort(base.begin(), base.end(), cmp);
vector<int> red, blue;
for (int i = 0; i < S; i++)
red.push_back(X[i]);
for (int i = 0; i < T; i++)
blue.push_back(Y[i]);
return Solve(base, red, blue);
}
Compilation message
factories.cpp:23:5: warning: built-in function 'log2' declared as non-function [-Wbuiltin-declaration-mismatch]
23 | int log2[2 * NMAX + 2];
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
28268 KB |
Output is correct |
2 |
Correct |
1652 ms |
37356 KB |
Output is correct |
3 |
Correct |
1779 ms |
37100 KB |
Output is correct |
4 |
Correct |
1661 ms |
37736 KB |
Output is correct |
5 |
Correct |
1430 ms |
47084 KB |
Output is correct |
6 |
Correct |
1221 ms |
46976 KB |
Output is correct |
7 |
Correct |
1765 ms |
46488 KB |
Output is correct |
8 |
Correct |
1661 ms |
46828 KB |
Output is correct |
9 |
Correct |
1425 ms |
47084 KB |
Output is correct |
10 |
Correct |
1225 ms |
46700 KB |
Output is correct |
11 |
Correct |
1768 ms |
46828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
28012 KB |
Output is correct |
2 |
Correct |
2259 ms |
163400 KB |
Output is correct |
3 |
Correct |
2496 ms |
167060 KB |
Output is correct |
4 |
Correct |
1806 ms |
182140 KB |
Output is correct |
5 |
Correct |
2169 ms |
218992 KB |
Output is correct |
6 |
Correct |
2741 ms |
187340 KB |
Output is correct |
7 |
Correct |
2611 ms |
76876 KB |
Output is correct |
8 |
Correct |
1594 ms |
76564 KB |
Output is correct |
9 |
Correct |
1635 ms |
81764 KB |
Output is correct |
10 |
Correct |
2544 ms |
78016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
28268 KB |
Output is correct |
2 |
Correct |
1652 ms |
37356 KB |
Output is correct |
3 |
Correct |
1779 ms |
37100 KB |
Output is correct |
4 |
Correct |
1661 ms |
37736 KB |
Output is correct |
5 |
Correct |
1430 ms |
47084 KB |
Output is correct |
6 |
Correct |
1221 ms |
46976 KB |
Output is correct |
7 |
Correct |
1765 ms |
46488 KB |
Output is correct |
8 |
Correct |
1661 ms |
46828 KB |
Output is correct |
9 |
Correct |
1425 ms |
47084 KB |
Output is correct |
10 |
Correct |
1225 ms |
46700 KB |
Output is correct |
11 |
Correct |
1768 ms |
46828 KB |
Output is correct |
12 |
Correct |
23 ms |
28012 KB |
Output is correct |
13 |
Correct |
2259 ms |
163400 KB |
Output is correct |
14 |
Correct |
2496 ms |
167060 KB |
Output is correct |
15 |
Correct |
1806 ms |
182140 KB |
Output is correct |
16 |
Correct |
2169 ms |
218992 KB |
Output is correct |
17 |
Correct |
2741 ms |
187340 KB |
Output is correct |
18 |
Correct |
2611 ms |
76876 KB |
Output is correct |
19 |
Correct |
1594 ms |
76564 KB |
Output is correct |
20 |
Correct |
1635 ms |
81764 KB |
Output is correct |
21 |
Correct |
2544 ms |
78016 KB |
Output is correct |
22 |
Correct |
5224 ms |
184040 KB |
Output is correct |
23 |
Correct |
4386 ms |
183332 KB |
Output is correct |
24 |
Correct |
5919 ms |
189532 KB |
Output is correct |
25 |
Correct |
5468 ms |
192484 KB |
Output is correct |
26 |
Correct |
5600 ms |
178656 KB |
Output is correct |
27 |
Correct |
4603 ms |
209616 KB |
Output is correct |
28 |
Correct |
3345 ms |
181384 KB |
Output is correct |
29 |
Correct |
5206 ms |
177080 KB |
Output is correct |
30 |
Correct |
5109 ms |
176712 KB |
Output is correct |
31 |
Correct |
5093 ms |
177556 KB |
Output is correct |
32 |
Correct |
2585 ms |
88444 KB |
Output is correct |
33 |
Correct |
2023 ms |
84312 KB |
Output is correct |
34 |
Correct |
3079 ms |
75652 KB |
Output is correct |
35 |
Correct |
3024 ms |
75380 KB |
Output is correct |
36 |
Correct |
3389 ms |
76252 KB |
Output is correct |
37 |
Correct |
3329 ms |
76080 KB |
Output is correct |