// CF template, version 3.0
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}
// #define int long long int
int power2(int v) {
return 1<<__lg(v - 1) + 1;
}
struct LazySegtree {
int n;
vector<long long> tree;
vector<long long> lazy;
vector<long long> initial;
LazySegtree(int N, vector<long long>& given)
: n(power2(N)), tree(2 * n), lazy(2 * n) {
forto(N, i) initial.push_back(given[i]);
}
void apply(long long add, int v) {
tree[v] += add;
lazy[v] += add;
}
void propagate(int v) {
apply(lazy[v], 2 * v);
apply(lazy[v], 2 * v + 1);
lazy[v] = 0;
}
void build(int v, int l, int r) {
if (l == r) {
tree[v] = initial[l];
} else {
int middle = (l + r) / 2;
build(2 * v, l, middle);
build(2 * v + 1, middle + 1, r);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
}
void upd(int ql, int qr, long long add, int v, int l, int r) {
if (ql <= l && r <= qr) {
apply(add, v);
} else if (qr < l || r < ql) {
return;
} else {
propagate(v);
int middle = (l + r) / 2;
upd(ql, qr, add, 2 * v, l, middle);
upd(ql, qr, add, 2 * v + 1, middle + 1, r);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
}
long long query(int ql, int qr, int v, int l, int r) {
if (ql <= l && r <= qr) {
return tree[v];
} else if (qr < l || r < ql) {
return 3e18;
} else {
propagate(v);
int middle = (l + r) / 2;
long long left = query(ql, qr, 2 * v, l, middle);
long long right = query(ql, qr, 2 * v + 1, middle + 1, r);
return min(left, right);
}
}
};
vector<vector<array<int, 2>>> adjList;
vector<bool> visited;
vector<long long> height;
vector<vector<int>> paths;
vector<int> sz;
vector<bool> upward;
vector<bool> downward;
vector<int> parent;
vector<int> indices;
vector<int> which;
vector<LazySegtree> segtrees;
void findvals(int v, int p, int w) {
visited[v] = true;
if (p == -1) {
height[v] = 0;
} else {
height[v] = height[p] + w;
}
sz[v] = 1;
int maxsz = 0;
int maxnode = 0;
for (array<int, 2> con: adjList[v]) {
int node = con[0];
int weight = con[1];
if (!visited[node]) {
findvals(node, v, weight);
sz[v] += sz[node];
parent[node] = v;
if (sz[node] > maxsz) {
maxsz = sz[node];
maxnode = node;
}
}
}
if (maxsz >= (sz[v] + 1) / 2) {
upward[maxnode] = true;
downward[v] = true;
}
}
void hld() {
int n = adjList.size();
int cnt = 0;
forto(n, i) {
if (!downward[i]) {
vector<int> path;
vector<long long> heights;
int node = i;
path.push_back(node);
heights.push_back(-2LL * height[node]);
indices[node] = 0;
which[node] = cnt;
int c = 0;
while (upward[node]) {
node = parent[node];
path.push_back(node);
heights.push_back(-2LL * height[node]);
indices[node] = ++c;
which[node] = cnt;
}
paths.push_back(path);
LazySegtree tree(path.size(), heights);
tree.build(1, 0, path.size() - 1);
segtrees.push_back(tree);
cnt++;
}
}
}
void Init(int n, int A[], int B[], int D[]) {
adjList.resize(n);
forto(n - 1, i) {
int a = A[i];
int b = B[i];
int d = D[i];
adjList[a].push_back({b, d});
adjList[b].push_back({a, d});
}
visited.resize(n, false);
height.resize(n);
sz.resize(n);
upward.resize(n, false);
downward.resize(n, false);
parent.resize(n, -1);
indices.resize(n);
which.resize(n);
findvals(0, -1, -1);
hld();
}
long long Query(int S, int X[], int T, int Y[]) {
vector<array<long long, 2>> sorted;
forto(T, i) {
sorted.push_back({height[Y[i]], Y[i]});
}
sortl(sorted);
vector<array<long long, 4>> updates;
for (array<long long, 2> p: sorted) {
long long h = p[0];
int node = p[1];
int thepath = which[node];
int index = indices[node];
while (1) {
int last = paths[thepath].back();
int sz = paths[thepath].size();
if (segtrees[thepath].query(index, index, 1, 0, sz - 1) != -2LL * height[paths[thepath][index]]) break;
if (segtrees[thepath].query(sz - 1, sz - 1, 1, 0, sz - 1) != -2LL * height[last]) {
int l = index;
int r = sz;
while (r - l > 1) {
int middle = (l + r) / 2;
if (segtrees[thepath].query(middle, middle, 1, 0, sz - 1) != -2LL * height[paths[thepath][middle]]) r = middle;
else l = middle;
}
segtrees[thepath].upd(index, l, h - (long long) 1e18, 1, 0, sz - 1);
updates.push_back({thepath, index, l, -h + (long long) 1e18});
break;
} else {
segtrees[thepath].upd(index, sz - 1, h - (long long) 1e18, 1, 0, sz - 1);
updates.push_back({thepath, index, sz - 1, -h + (long long) 1e18});
if (last == 0) {
break;
}
int next = parent[last];
thepath = which[next];
index = indices[next];
}
}
}
long long ans = 3e18;
forto(S, i) {
long long h = height[X[i]];
int node = X[i];
long long from = 3e18;
int thepath = which[node];
int index = indices[node];
while (1) {
int last = paths[thepath].back();
int sz = paths[thepath].size();
from = min(from, segtrees[thepath].query(index, sz - 1, 1, 0, sz - 1) + h + (long long) 1e18);
if (last == 0) {
break;
}
int next = parent[last];
thepath = which[next];
index = indices[next];
}
ans = min(ans, from);
}
for (array<long long, 4> update: updates) {
int thepath = update[0];
int l = update[1];
int r = update[2];
long long add = update[3];
int sz = paths[thepath].size();
segtrees[thepath].upd(l, r, add, 1, 0, sz - 1);
}
return ans;
}
Compilation message
factories.cpp: In function 'int power2(int)':
factories.cpp:22:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
22 | return 1<<__lg(v - 1) + 1;
| ~~~~~~~~~~~~^~~
factories.cpp: In constructor 'LazySegtree::LazySegtree(int, std::vector<long long int>&)':
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
factories.cpp:33:9: note: in expansion of macro 'forto'
33 | forto(N, i) initial.push_back(given[i]);
| ^~~~~
factories.cpp: In function 'void hld()':
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
factories.cpp:131:5: note: in expansion of macro 'forto'
131 | forto(n, i) {
| ^~~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
factories.cpp:159:5: note: in expansion of macro 'forto'
159 | forto(n - 1, i) {
| ^~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
factories.cpp:180:5: note: in expansion of macro 'forto'
180 | forto(T, i) {
| ^~~~~
factories.cpp:16:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
16 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
factories.cpp:218:5: note: in expansion of macro 'forto'
218 | forto(S, i) {
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
169 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
160 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
169 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
