#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define BIT(x, i) ((x) >> (i) & 1)
#define MASK(i) (1LL << (i))
#define left ___left
#define right ___right
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i-- > 0; )
#define FOR(i, a, b) for (int _b = (b), i = (a); i < _b; ++i)
#define FORD(i, b, a) for (int _a = (a), i = (b); i-- > _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; }
template <class T> scan_op(vector <T>) { for (T &x: u) in >> x; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << "(" << u.fi << ", " << u.se << ")"; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>> (out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &u) { out << "{"; for (auto it = u.begin(); it != u.end(); ++it) out << (it == u.begin() ? "" : ", ") << *it; return out << "}"; }
struct Fenwick {
vector <long long> bit;
int N;
Fenwick(int n = 0) {
N = n;
bit.resize(N + 1, 0);
}
void update(int i, long long val) {
for (; i <= N; i += i & -i) bit[i] += val;
}
void update(int l, int r, long long val) {
update(l, val);
update(r + 1, -val);
}
long long get(int i) {
long long res = 0;
for (; i > 0; i &= i - 1) res += bit[i];
return res;
}
long long get(int l, int r) {
return get(r) - get(l - 1);
}
int lower_bound(long long val) {
int res = 0;
REPD(i, __lg(N) + 1) if ((res ^ MASK(i)) <= N && val > bit[res ^ MASK(i)]) {
res ^= MASK(i);
val -= bit[res];
}
return res + 1;
}
};
const int MAX = 1e5 + 5;
const int LOG = 17;
int N, W[MAX], tin[MAX], tout[MAX], anc[MAX][LOG], T[MAX], timeDfs, depth[MAX], pos[MAX], treeSize[MAX];
long long length[MAX];
vector <pair <int, int>> adj[MAX];
long long sum_all, t_res;
Fenwick sum;
void dfs(int u) {
tin[u] = ++timeDfs;
pos[timeDfs] = u;
FOR(i, 1, LOG) anc[u][i] = anc[anc[u][i - 1]][i - 1];
depth[u] = depth[anc[u][0]] + 1;
treeSize[u] = 1;
for (auto [t, v]: adj[u]) if (v != anc[u][0]) {
T[v] = t;
anc[v][0] = u;
length[v] = length[u] + t;
dfs(v);
treeSize[u] += treeSize[v];
}
tout[u] = timeDfs;
}
int headHLD[MAX], depthHLD[MAX], posHLD[MAX], numBase, inv_posHLD[MAX];
void hld(int u) {
posHLD[u] = ++numBase;
inv_posHLD[numBase] = u;
int heavy = -1;
for (auto [t, v]: adj[u]) if (v != anc[u][0] && (heavy == -1 || treeSize[heavy] < treeSize[v])) heavy = v;
if (heavy != -1) {
headHLD[heavy] = headHLD[u];
depthHLD[heavy] = depthHLD[u];
hld(heavy);
}
for (auto [t, v]: adj[u]) if (v != anc[u][0] && v != heavy) {
headHLD[v] = v;
depthHLD[v] = depthHLD[u] + 1;
hld(v);
}
}
long long st[MAX << 2], lazy[MAX << 2];
void pushDown(int i, int l, int r) {
int m = l + r >> 1;
if (lazy[i]) {
st[i << 1] += lazy[i] * (length[inv_posHLD[m]] - length[anc[inv_posHLD[l]][0]]);
lazy[i << 1] += lazy[i];
st[i << 1 | 1] += lazy[i] * (length[inv_posHLD[r]] - length[anc[inv_posHLD[m + 1]][0]]);
lazy[i << 1 | 1] += lazy[i];
lazy[i] = 0;
}
}
void update(int i, int l, int r, int u, int v, int val) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
st[i] += val * (length[inv_posHLD[r]] - length[anc[inv_posHLD[l]][0]]);
lazy[i] += val;
return;
}
int m = l + r >> 1;
pushDown(i, l, r);
update(i << 1, l, m, u, v, val);
update(i << 1 | 1, m + 1, r, u, v, val);
st[i] = st[i << 1] + st[i << 1 | 1];
}
long long get(int i, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (u <= l && r <= v) return st[i];
int m = l + r >> 1;
pushDown(i, l, r);
return get(i << 1, l, m, u, v) + get(i << 1 | 1, m + 1, r, u, v);
}
void update(int u, int add) {
while (headHLD[u]) {
update(1, 1, N, posHLD[headHLD[u]], posHLD[u], add);
u = anc[headHLD[u]][0];
}
update(1, 1, N, posHLD[0], posHLD[u], add);
}
long long get(int u) {
long long res = 0;
while (headHLD[u]) {
res += get(1, 1, N, posHLD[headHLD[u]], posHLD[u]);
u = anc[headHLD[u]][0];
}
res += get(1, 1, N, posHLD[0], posHLD[u]);
return res;
}
void init(int _N, vector <int> U, vector <int> V, vector <int> T, vector <int> _W) {
N = _N;
REP(i, N - 1) {
adj[U[i]].emplace_back(T[i], V[i]);
adj[V[i]].emplace_back(T[i], U[i]);
}
REP(i, N) {
W[i] = _W[i];
sum_all += W[i];
}
dfs(0);
sum = Fenwick(N);
hld(0);
REP(u, N) {
sum.update(tin[u], W[u]);
update(u, W[u]);
t_res += W[u] * length[u];
}
}
long long max_time(int u, int X) {
int add = X - W[u];
W[u] = X;
sum_all += add;
sum.update(tin[u], add);
update(u, add);
t_res += add * length[u];
long long mid = sum_all / 2 + 1;
u = pos[sum.lower_bound(mid)];
if (sum.get(tin[u], tout[u]) < mid) {
REPD(i, LOG) if (sum.get(tin[anc[u][i]], tout[anc[u][i]]) < mid) u = anc[u][i];
u = anc[u][0];
}
return (t_res + (sum_all + 1) * length[u] - 2 * get(u)) * 2;
}
Compilation message
deliveries.cpp: In function 'void pushDown(int, int, int)':
deliveries.cpp:109:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int m = l + r >> 1;
| ~~^~~
deliveries.cpp: In function 'void update(int, int, int, int, int, int)':
deliveries.cpp:126:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
126 | int m = l + r >> 1;
| ~~^~~
deliveries.cpp: In function 'long long int get(int, int, int, int, int)':
deliveries.cpp:136:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
136 | int m = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
18548 KB |
Output is correct |
2 |
Correct |
81 ms |
18260 KB |
Output is correct |
3 |
Correct |
76 ms |
18512 KB |
Output is correct |
4 |
Correct |
75 ms |
18528 KB |
Output is correct |
5 |
Correct |
76 ms |
18512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8540 KB |
Output is correct |
2 |
Correct |
3 ms |
8792 KB |
Output is correct |
3 |
Correct |
4 ms |
8796 KB |
Output is correct |
4 |
Correct |
3 ms |
8860 KB |
Output is correct |
5 |
Correct |
3 ms |
8796 KB |
Output is correct |
6 |
Correct |
2 ms |
8796 KB |
Output is correct |
7 |
Correct |
3 ms |
8796 KB |
Output is correct |
8 |
Correct |
4 ms |
8952 KB |
Output is correct |
9 |
Correct |
3 ms |
8796 KB |
Output is correct |
10 |
Correct |
2 ms |
8796 KB |
Output is correct |
11 |
Correct |
4 ms |
8796 KB |
Output is correct |
12 |
Correct |
3 ms |
8796 KB |
Output is correct |
13 |
Correct |
3 ms |
8796 KB |
Output is correct |
14 |
Correct |
3 ms |
8796 KB |
Output is correct |
15 |
Correct |
4 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
18548 KB |
Output is correct |
2 |
Correct |
81 ms |
18260 KB |
Output is correct |
3 |
Correct |
76 ms |
18512 KB |
Output is correct |
4 |
Correct |
75 ms |
18528 KB |
Output is correct |
5 |
Correct |
76 ms |
18512 KB |
Output is correct |
6 |
Correct |
2 ms |
8536 KB |
Output is correct |
7 |
Correct |
6 ms |
8796 KB |
Output is correct |
8 |
Correct |
75 ms |
13648 KB |
Output is correct |
9 |
Correct |
1060 ms |
39204 KB |
Output is correct |
10 |
Correct |
1081 ms |
39204 KB |
Output is correct |
11 |
Correct |
1024 ms |
39472 KB |
Output is correct |
12 |
Correct |
785 ms |
41780 KB |
Output is correct |
13 |
Correct |
795 ms |
42184 KB |
Output is correct |
14 |
Correct |
874 ms |
41916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
18548 KB |
Output is correct |
2 |
Correct |
81 ms |
18260 KB |
Output is correct |
3 |
Correct |
76 ms |
18512 KB |
Output is correct |
4 |
Correct |
75 ms |
18528 KB |
Output is correct |
5 |
Correct |
76 ms |
18512 KB |
Output is correct |
6 |
Correct |
3 ms |
8540 KB |
Output is correct |
7 |
Correct |
5 ms |
9052 KB |
Output is correct |
8 |
Correct |
28 ms |
14416 KB |
Output is correct |
9 |
Correct |
419 ms |
47084 KB |
Output is correct |
10 |
Correct |
437 ms |
47012 KB |
Output is correct |
11 |
Correct |
384 ms |
47052 KB |
Output is correct |
12 |
Correct |
388 ms |
50176 KB |
Output is correct |
13 |
Correct |
359 ms |
50104 KB |
Output is correct |
14 |
Correct |
261 ms |
46272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
18548 KB |
Output is correct |
2 |
Correct |
81 ms |
18260 KB |
Output is correct |
3 |
Correct |
76 ms |
18512 KB |
Output is correct |
4 |
Correct |
75 ms |
18528 KB |
Output is correct |
5 |
Correct |
76 ms |
18512 KB |
Output is correct |
6 |
Correct |
2 ms |
8540 KB |
Output is correct |
7 |
Correct |
3 ms |
8792 KB |
Output is correct |
8 |
Correct |
4 ms |
8796 KB |
Output is correct |
9 |
Correct |
3 ms |
8860 KB |
Output is correct |
10 |
Correct |
3 ms |
8796 KB |
Output is correct |
11 |
Correct |
2 ms |
8796 KB |
Output is correct |
12 |
Correct |
3 ms |
8796 KB |
Output is correct |
13 |
Correct |
4 ms |
8952 KB |
Output is correct |
14 |
Correct |
3 ms |
8796 KB |
Output is correct |
15 |
Correct |
2 ms |
8796 KB |
Output is correct |
16 |
Correct |
4 ms |
8796 KB |
Output is correct |
17 |
Correct |
3 ms |
8796 KB |
Output is correct |
18 |
Correct |
3 ms |
8796 KB |
Output is correct |
19 |
Correct |
3 ms |
8796 KB |
Output is correct |
20 |
Correct |
4 ms |
8796 KB |
Output is correct |
21 |
Correct |
2 ms |
8536 KB |
Output is correct |
22 |
Correct |
6 ms |
8796 KB |
Output is correct |
23 |
Correct |
75 ms |
13648 KB |
Output is correct |
24 |
Correct |
1060 ms |
39204 KB |
Output is correct |
25 |
Correct |
1081 ms |
39204 KB |
Output is correct |
26 |
Correct |
1024 ms |
39472 KB |
Output is correct |
27 |
Correct |
785 ms |
41780 KB |
Output is correct |
28 |
Correct |
795 ms |
42184 KB |
Output is correct |
29 |
Correct |
874 ms |
41916 KB |
Output is correct |
30 |
Correct |
3 ms |
8540 KB |
Output is correct |
31 |
Correct |
5 ms |
9052 KB |
Output is correct |
32 |
Correct |
28 ms |
14416 KB |
Output is correct |
33 |
Correct |
419 ms |
47084 KB |
Output is correct |
34 |
Correct |
437 ms |
47012 KB |
Output is correct |
35 |
Correct |
384 ms |
47052 KB |
Output is correct |
36 |
Correct |
388 ms |
50176 KB |
Output is correct |
37 |
Correct |
359 ms |
50104 KB |
Output is correct |
38 |
Correct |
261 ms |
46272 KB |
Output is correct |
39 |
Correct |
2 ms |
8536 KB |
Output is correct |
40 |
Correct |
6 ms |
8796 KB |
Output is correct |
41 |
Correct |
43 ms |
14164 KB |
Output is correct |
42 |
Correct |
600 ms |
43316 KB |
Output is correct |
43 |
Correct |
540 ms |
44208 KB |
Output is correct |
44 |
Correct |
518 ms |
45108 KB |
Output is correct |
45 |
Correct |
516 ms |
45624 KB |
Output is correct |
46 |
Correct |
546 ms |
46496 KB |
Output is correct |
47 |
Correct |
500 ms |
45876 KB |
Output is correct |
48 |
Correct |
509 ms |
46628 KB |
Output is correct |
49 |
Correct |
503 ms |
47236 KB |
Output is correct |
50 |
Correct |
492 ms |
47944 KB |
Output is correct |
51 |
Correct |
456 ms |
48436 KB |
Output is correct |
52 |
Correct |
657 ms |
41520 KB |
Output is correct |
53 |
Correct |
652 ms |
41608 KB |
Output is correct |
54 |
Correct |
650 ms |
41508 KB |
Output is correct |
55 |
Correct |
457 ms |
45108 KB |
Output is correct |
56 |
Correct |
486 ms |
45908 KB |
Output is correct |
57 |
Correct |
498 ms |
45704 KB |
Output is correct |