#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <set>
#define int long long
#define log2(x) (sizeof(long long)*8 - __builtin_clzll(x))
using namespace std;
struct segtree
{
vector<int> table;
vector<int> ops;
void apply(int pos, int val)
{
ops[pos] += val;
table[pos] += val;
}
void propagate(int pos)
{
apply(2*pos + 1, ops[pos]);
apply(2*pos + 2, ops[pos]);
ops[pos] = 0;
}
int query(int ql, int qr, int l, int r, int pos)
{
if (ql <= l && r <= qr) return table[pos];
if (r < ql || qr < l) return -1;
propagate(pos);
return max(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
}
void update(int ql, int qr, int val, int l, int r, int pos)
{
if (ql <= l && r <= qr)
{
apply(pos, val);
return;
}
if (r < ql || qr < l) return;
propagate(pos);
update(ql, qr, val, l, (l + r)/2, 2*pos + 1);
update(ql, qr, val, (l + r)/2 + 1, r, 2*pos + 2);
table[pos] = max(table[2*pos + 1], table[2*pos + 2]);
}
void build(const vector<int>& vs, int l, int r, int pos)
{
if (l == r)
{
table[pos] = vs[l];
return;
}
build(vs, l, (l + r)/2, 2*pos + 1);
build(vs, (l + r)/2 + 1, r, 2*pos + 2);
table[pos] = max(table[2*pos + 1], table[2*pos + 2]);
}
};
struct tree
{
int n;
int logn;
vector<vector<pair<int,int>>> adjlist;
vector<vector<int>> prein;
vector<vector<int>> preout;
vector<vector<int>> root;
vector<vector<int>> desc;
vector<vector<int>> depth;
vector<int> sz;
vector<multiset<int, greater<int>>> tvals;
vector<segtree> trees;
multiset<int, greater<int>> mvals;
vector<int> lvl;
vector<pair<int,int>> edges;
vector<int> weights;
int getmx(int ms)
{
return (*tvals[ms].begin()) + (*next(tvals[ms].begin()));
}
int update(int ind, int val)
{
auto vp = edges[ind];
int mlv = min(lvl[vp.first], lvl[vp.second]);
int nd = val - weights[ind];
weights[ind] = val;
for (int i = 0; i <= mlv; i++)
{
int v = (depth[vp.first][i] < depth[vp.second][i] ? vp.second : vp.first);
int rt = root[v][i];
mvals.erase(mvals.find(getmx(rt)));
int dsc = desc[v][i];
int sv = trees[rt].query(prein[dsc][i], preout[dsc][i], 0, sz[rt] - 1, 0);
tvals[rt].erase(tvals[rt].find(sv));
trees[rt].update(prein[v][i], preout[v][i], nd, 0, sz[rt] - 1, 0);
sv = trees[rt].query(prein[dsc][i], preout[dsc][i], 0, sz[rt] - 1, 0);
tvals[rt].insert(sv);
mvals.insert(getmx(rt));
}
return *mvals.begin();
}
void prefdfs(int curr, int par, int lv, int& ord, int dsc, int dpth, vector<int>& dsts, int dist, int rt)
{
if (lvl[curr] < lv) return;
root[curr][lv] = rt;
prein[curr][lv] = ord;
desc[curr][lv] = dsc;
depth[curr][lv] = dpth;
dsts.push_back(dist);
ord++;
for (auto np : adjlist[curr])
{
int next = np.first;
if (next == par) continue;
prefdfs(next, curr, lv, ord, (dsc == -1 ? next : dsc), dpth + 1, dsts, dist + np.second, rt);
}
preout[curr][lv] = ord - 1;
}
void precalcdia()
{
logn = log2(n);
prein.resize(n, vector<int>(logn, -1));
preout.resize(n, vector<int>(logn, -1));
root.resize(n, vector<int>(logn, -1));
desc.resize(n, vector<int>(logn, -1));
depth.resize(n, vector<int>(logn, -1));
sz.resize(n, -1);
tvals.resize(n);
trees.resize(n);
lvl.resize(n, -1);
for (int i = 0; i < n; i++)
{
vector<int> ds;
int ord = 0;
int lv = lvl[i];
prefdfs(i, -1, lv, ord, -1, 0, ds, 0, i);
trees[i].table.resize(4*ord, -1);
trees[i].ops.resize(4*ord, 0);
trees[i].build(ds, 0, ord - 1, 0);
tvals[i].insert(0);
tvals[i].insert(0);
sz[i] = ord;
for (auto np : adjlist[i])
{
int next = np.first;
if (lvl[next] < lv) continue;
int sv = trees[i].query(prein[next][lv], preout[next][lv], 0, ord - 1, 0);
tvals[i].insert(sv);
}
mvals.insert(getmx(i));
}
}
vector<int> ssz;
int szdfs(int curr, int par)
{
if (lvl[curr] != -1) return 0;
ssz[curr] = 1;
for (auto np : adjlist[curr])
{
int next = np.first;
if (next == par) continue;
ssz[curr] += szdfs(next, curr);
}
return ssz[curr];
}
int cntdfs(int curr, int par, int sbz)
{
for (auto np : adjlist[curr])
{
int next = np.first;
if (next == par || lvl[next] != -1) continue;
if (ssz[next] > sbz / 2) return cntdfs(next, curr, sbz);
}
return curr;
}
void findcentroid(int nrt, int lv)
{
szdfs(nrt, -1);
int cent = cntdfs(nrt, -1, ssz[nrt]);
lvl[cent] = lv;
for (auto np : adjlist[cent])
{
int next = np.first;
if (lvl[next] == -1) findcentroid(next, lv + 1);
}
}
void precalc()
{
lvl.resize(n, - 1);
ssz.resize(n, -1);
findcentroid(0, 0);
precalcdia();
// print();
}
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q, m;
cin >> n >> q >> m;
tree t;
t.n = n;
t.adjlist.resize(n);
t.edges.resize(n - 1);
t.weights.resize(n - 1);
for (int i = 0; i < n - 1; i++)
{
int a, b, w;
cin >> a >> b >> w;
a--; b--;
t.edges[i] = make_pair(a, b);
t.weights[i] = w;
t.adjlist[a].emplace_back(b, w);
t.adjlist[b].emplace_back(a, w);
}
t.precalc();
int last = 0;
for (int i = 0; i < q; i++)
{
int d, e;
cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % m;
last = t.update(d, e);
cout << last << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
24 ms |
1792 KB |
Output is correct |
20 |
Correct |
31 ms |
1848 KB |
Output is correct |
21 |
Correct |
31 ms |
1920 KB |
Output is correct |
22 |
Correct |
36 ms |
2048 KB |
Output is correct |
23 |
Correct |
98 ms |
8056 KB |
Output is correct |
24 |
Correct |
89 ms |
8724 KB |
Output is correct |
25 |
Correct |
155 ms |
9080 KB |
Output is correct |
26 |
Correct |
97 ms |
9848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
14 ms |
384 KB |
Output is correct |
5 |
Correct |
70 ms |
788 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
896 KB |
Output is correct |
8 |
Correct |
2 ms |
896 KB |
Output is correct |
9 |
Correct |
5 ms |
896 KB |
Output is correct |
10 |
Correct |
25 ms |
948 KB |
Output is correct |
11 |
Correct |
120 ms |
1400 KB |
Output is correct |
12 |
Correct |
12 ms |
6400 KB |
Output is correct |
13 |
Correct |
11 ms |
6400 KB |
Output is correct |
14 |
Correct |
21 ms |
6528 KB |
Output is correct |
15 |
Correct |
45 ms |
6528 KB |
Output is correct |
16 |
Correct |
229 ms |
7032 KB |
Output is correct |
17 |
Correct |
326 ms |
138188 KB |
Output is correct |
18 |
Correct |
304 ms |
138216 KB |
Output is correct |
19 |
Correct |
281 ms |
138088 KB |
Output is correct |
20 |
Correct |
388 ms |
138228 KB |
Output is correct |
21 |
Correct |
839 ms |
138840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
1920 KB |
Output is correct |
2 |
Correct |
38 ms |
1920 KB |
Output is correct |
3 |
Correct |
178 ms |
2168 KB |
Output is correct |
4 |
Correct |
389 ms |
2424 KB |
Output is correct |
5 |
Correct |
60 ms |
19340 KB |
Output is correct |
6 |
Correct |
117 ms |
19368 KB |
Output is correct |
7 |
Correct |
502 ms |
19632 KB |
Output is correct |
8 |
Correct |
972 ms |
19924 KB |
Output is correct |
9 |
Correct |
367 ms |
106476 KB |
Output is correct |
10 |
Correct |
432 ms |
106676 KB |
Output is correct |
11 |
Correct |
952 ms |
106988 KB |
Output is correct |
12 |
Correct |
1444 ms |
107116 KB |
Output is correct |
13 |
Correct |
633 ms |
219108 KB |
Output is correct |
14 |
Correct |
807 ms |
218944 KB |
Output is correct |
15 |
Correct |
1502 ms |
219388 KB |
Output is correct |
16 |
Correct |
2435 ms |
219784 KB |
Output is correct |
17 |
Correct |
3934 ms |
219604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4328 ms |
195984 KB |
Output is correct |
2 |
Correct |
4406 ms |
198728 KB |
Output is correct |
3 |
Correct |
3861 ms |
197800 KB |
Output is correct |
4 |
Correct |
4021 ms |
198452 KB |
Output is correct |
5 |
Correct |
3919 ms |
193800 KB |
Output is correct |
6 |
Correct |
3338 ms |
170288 KB |
Output is correct |
7 |
Execution timed out |
5064 ms |
222488 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
24 ms |
1792 KB |
Output is correct |
20 |
Correct |
31 ms |
1848 KB |
Output is correct |
21 |
Correct |
31 ms |
1920 KB |
Output is correct |
22 |
Correct |
36 ms |
2048 KB |
Output is correct |
23 |
Correct |
98 ms |
8056 KB |
Output is correct |
24 |
Correct |
89 ms |
8724 KB |
Output is correct |
25 |
Correct |
155 ms |
9080 KB |
Output is correct |
26 |
Correct |
97 ms |
9848 KB |
Output is correct |
27 |
Correct |
0 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
14 ms |
384 KB |
Output is correct |
31 |
Correct |
70 ms |
788 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
896 KB |
Output is correct |
34 |
Correct |
2 ms |
896 KB |
Output is correct |
35 |
Correct |
5 ms |
896 KB |
Output is correct |
36 |
Correct |
25 ms |
948 KB |
Output is correct |
37 |
Correct |
120 ms |
1400 KB |
Output is correct |
38 |
Correct |
12 ms |
6400 KB |
Output is correct |
39 |
Correct |
11 ms |
6400 KB |
Output is correct |
40 |
Correct |
21 ms |
6528 KB |
Output is correct |
41 |
Correct |
45 ms |
6528 KB |
Output is correct |
42 |
Correct |
229 ms |
7032 KB |
Output is correct |
43 |
Correct |
326 ms |
138188 KB |
Output is correct |
44 |
Correct |
304 ms |
138216 KB |
Output is correct |
45 |
Correct |
281 ms |
138088 KB |
Output is correct |
46 |
Correct |
388 ms |
138228 KB |
Output is correct |
47 |
Correct |
839 ms |
138840 KB |
Output is correct |
48 |
Correct |
16 ms |
1920 KB |
Output is correct |
49 |
Correct |
38 ms |
1920 KB |
Output is correct |
50 |
Correct |
178 ms |
2168 KB |
Output is correct |
51 |
Correct |
389 ms |
2424 KB |
Output is correct |
52 |
Correct |
60 ms |
19340 KB |
Output is correct |
53 |
Correct |
117 ms |
19368 KB |
Output is correct |
54 |
Correct |
502 ms |
19632 KB |
Output is correct |
55 |
Correct |
972 ms |
19924 KB |
Output is correct |
56 |
Correct |
367 ms |
106476 KB |
Output is correct |
57 |
Correct |
432 ms |
106676 KB |
Output is correct |
58 |
Correct |
952 ms |
106988 KB |
Output is correct |
59 |
Correct |
1444 ms |
107116 KB |
Output is correct |
60 |
Correct |
633 ms |
219108 KB |
Output is correct |
61 |
Correct |
807 ms |
218944 KB |
Output is correct |
62 |
Correct |
1502 ms |
219388 KB |
Output is correct |
63 |
Correct |
2435 ms |
219784 KB |
Output is correct |
64 |
Correct |
3934 ms |
219604 KB |
Output is correct |
65 |
Correct |
4328 ms |
195984 KB |
Output is correct |
66 |
Correct |
4406 ms |
198728 KB |
Output is correct |
67 |
Correct |
3861 ms |
197800 KB |
Output is correct |
68 |
Correct |
4021 ms |
198452 KB |
Output is correct |
69 |
Correct |
3919 ms |
193800 KB |
Output is correct |
70 |
Correct |
3338 ms |
170288 KB |
Output is correct |
71 |
Execution timed out |
5064 ms |
222488 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |