//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 17;
const int mod = 998244353;
struct Tree{
vector<int>tab, lazy;
int size = 1;
Tree(int n){
while (size < n) size*=2;
tab.assign(2*size, -oo);
lazy.assign(2*size, 0);
}
//dodaj na przedziale max na przedziale
void update(int x, int lx, int rx, int pos, int val){
if (lx == rx) {
tab[x] = val;
return;
}
int m = (lx+rx)/2;
push(x);
if (pos <= m) update(2*x, lx, m, pos, val);
else update(2*x+1, m+1, rx, pos, val);
tab[x] = max(tab[2*x], tab[2*x+1]);
}
void update(int x, int lx, int rx, int l, int r, int val){
if (lx > r || rx < l) return;
if (lx >= l && rx <= r){
tab[x] += val;
lazy[x] += val;
return;
}
int m = (lx+rx)/2;
push(x);
update(2*x, lx, m, l, r, val);
update(2*x+1, m+1, rx, l, r, val);
tab[x] = max(tab[2*x], tab[2*x+1]);
}
void push(int x){
if (!lazy[x]) return;
for (auto k: {2*x, 2*x+1}){
tab[k] += lazy[x];
lazy[k] += lazy[x];
}
lazy[x] = 0;
}
int query(int x, int lx, int rx, int l, int r){
if (lx > r || rx < l) return -oo;
if (lx >= l && rx <= r) return tab[x];
int m = (lx+rx)/2;
push(x);
return max(query(2*x, lx, m, l, r), query(2*x+1, m+1, rx, l, r));
}
};
void solve(){
int n, q, w; cin >> n >> q >> w;
vector<vector<T>>g(n+1);
vector<int>cost(n);
for (int i = 1; i<n; i++){
int a, b; cin >> a >> b >> cost[i];
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
vector<int>sz(n+1), pre(n+1);
vector<bool>vis(n+1);
int tt = 0;
function<int(int, int)>getsz = [&](int v, int pa){
sz[v] = 1;
for (auto [x, i]: g[v]){
if (x == pa || vis[x]) continue;
sz[v] += getsz(x, v);
}
return sz[v];
};
function<int(int, int, int)>get_centroid = [&](int v, int pa, int ms){
for (auto [x, i]: g[v]){
if (x == pa || vis[x]) continue;
if (2*sz[x] > ms) return get_centroid(x, v, ms);
}
return v;
};
vector<T>ord;
vector<T>seg(n+1);
int all = 0;
map<T, T>pos;
Tree t(n * K);
vector<multiset<int>>vals(n+1);
vector<int>depth(n+1);
vector<vector<int>>where(n+1);
multiset<int>ans;
map<T, T>SZ;
auto get = [&](int c){
if ((int)vals[c].empty()) return -oo;
if ((int)vals[c].size() == 1) return *vals[c].rbegin();
debug(c, vals[c]);
auto it = --(vals[c].end());
int ans = *it;
it--;
ans += *it;
debug(ans);
return ans;
};
function<void(int)>centroid = [&](int c){
c = get_centroid(c, c, getsz(c, c));
getsz(c, c);
seg[c] = {all, all+sz[c]-2};
function<void(int, int, int)>dfs = [&](int v, int pa, int from){
for (auto [x, i]: g[v]){
if (x == pa || vis[x]) continue;
from = (v == pa ? x : from);
if (v == pa) SZ[{c, from}] = {sz[from], all};
pos[{c, i}] = {all++, from};
ord.emplace_back(x, sz[x]);
where[i].emplace_back(c);
depth[x] = depth[v] + cost[i];
t.update(1, 0, t.size-1, all-1, depth[x]);
dfs(x, v, from);
}
};
depth[c] = 0;
dfs(c, c, -1);
for (auto [x, i]: g[c]){
if (vis[x]) continue;
int l = pos[{c, i}].first;
int ll = ord[l].second;
if (ll >= 1) vals[c].insert(t.query(1, 0, t.size-1, l, l+ll-1));
}
ans.insert(get(c));
debug(c, vals[c]);
vis[c] = 1;
for (auto [x, i]: g[c]){
if (!vis[x]){
centroid(x);
}
}
};
centroid(1);
int last = 0;
debug(ans);
debug(ord);
while (q--){
int i, waga; cin >> i >> waga;
i = (i+last)%(n-1) + 1;
waga = (waga+last)%w;
debug(i, cost[i], waga);
int diff = waga - cost[i];
cost[i] = waga;
for (auto c: where[i]){
debug(c);
auto [l, from] = pos[{c, i}];
auto [v, s] = ord[l];
debug(l, from, v, s);
ans.erase(ans.find(get(c)));
auto [s2, ls] = SZ[{c, from}];
debug(from, ls, s2);
if (s2 >= 1){
int mx = t.query(1, 0, t.size-1, ls, ls+s2-1); //ale ja chce dla from
debug(mx);
vals[c].erase(vals[c].find(mx));
}
if (s >= 1) t.update(1, 0, t.size-1, l, l+s-1, diff);
if (s2 >= 1){
int mx = t.query(1, 0, t.size-1, ls, ls+s2-1); //ale ja chce dla from
debug(mx);
vals[c].insert(mx);
}
debug(vals[c], get(c));
ans.insert(get(c));
}
last = *ans.rbegin();
cout << last << "\n";
// return;
}
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
Compilation message
diameter.cpp: In function 'void solve()':
diameter.cpp:98:9: warning: unused variable 'tt' [-Wunused-variable]
98 | int tt = 0;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
608 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
608 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
25 ms |
2396 KB |
Output is correct |
20 |
Correct |
28 ms |
2396 KB |
Output is correct |
21 |
Correct |
38 ms |
2920 KB |
Output is correct |
22 |
Correct |
44 ms |
2900 KB |
Output is correct |
23 |
Correct |
52 ms |
9684 KB |
Output is correct |
24 |
Correct |
70 ms |
10876 KB |
Output is correct |
25 |
Correct |
82 ms |
11464 KB |
Output is correct |
26 |
Correct |
105 ms |
12720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
12 ms |
600 KB |
Output is correct |
5 |
Correct |
55 ms |
1456 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
1116 KB |
Output is correct |
9 |
Correct |
3 ms |
1260 KB |
Output is correct |
10 |
Correct |
18 ms |
1624 KB |
Output is correct |
11 |
Correct |
92 ms |
2664 KB |
Output is correct |
12 |
Correct |
8 ms |
7000 KB |
Output is correct |
13 |
Correct |
8 ms |
7000 KB |
Output is correct |
14 |
Correct |
10 ms |
7004 KB |
Output is correct |
15 |
Correct |
32 ms |
7208 KB |
Output is correct |
16 |
Correct |
124 ms |
8400 KB |
Output is correct |
17 |
Correct |
204 ms |
115880 KB |
Output is correct |
18 |
Correct |
194 ms |
115864 KB |
Output is correct |
19 |
Correct |
192 ms |
115904 KB |
Output is correct |
20 |
Correct |
238 ms |
116020 KB |
Output is correct |
21 |
Correct |
520 ms |
117440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
2652 KB |
Output is correct |
2 |
Correct |
42 ms |
2768 KB |
Output is correct |
3 |
Correct |
191 ms |
3336 KB |
Output is correct |
4 |
Correct |
388 ms |
4228 KB |
Output is correct |
5 |
Correct |
63 ms |
23744 KB |
Output is correct |
6 |
Correct |
139 ms |
24068 KB |
Output is correct |
7 |
Correct |
519 ms |
25024 KB |
Output is correct |
8 |
Correct |
905 ms |
25576 KB |
Output is correct |
9 |
Correct |
394 ms |
122668 KB |
Output is correct |
10 |
Correct |
508 ms |
121684 KB |
Output is correct |
11 |
Correct |
1312 ms |
122192 KB |
Output is correct |
12 |
Correct |
2052 ms |
122972 KB |
Output is correct |
13 |
Correct |
815 ms |
252072 KB |
Output is correct |
14 |
Correct |
952 ms |
252096 KB |
Output is correct |
15 |
Correct |
1885 ms |
252004 KB |
Output is correct |
16 |
Correct |
2995 ms |
254196 KB |
Output is correct |
17 |
Execution timed out |
5022 ms |
252136 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4555 ms |
217396 KB |
Output is correct |
2 |
Correct |
4712 ms |
220576 KB |
Output is correct |
3 |
Correct |
4658 ms |
219352 KB |
Output is correct |
4 |
Correct |
4687 ms |
220936 KB |
Output is correct |
5 |
Correct |
4624 ms |
213852 KB |
Output is correct |
6 |
Correct |
3935 ms |
172876 KB |
Output is correct |
7 |
Execution timed out |
5035 ms |
257836 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
608 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
25 ms |
2396 KB |
Output is correct |
20 |
Correct |
28 ms |
2396 KB |
Output is correct |
21 |
Correct |
38 ms |
2920 KB |
Output is correct |
22 |
Correct |
44 ms |
2900 KB |
Output is correct |
23 |
Correct |
52 ms |
9684 KB |
Output is correct |
24 |
Correct |
70 ms |
10876 KB |
Output is correct |
25 |
Correct |
82 ms |
11464 KB |
Output is correct |
26 |
Correct |
105 ms |
12720 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
2 ms |
348 KB |
Output is correct |
30 |
Correct |
12 ms |
600 KB |
Output is correct |
31 |
Correct |
55 ms |
1456 KB |
Output is correct |
32 |
Correct |
0 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
1116 KB |
Output is correct |
34 |
Correct |
1 ms |
1116 KB |
Output is correct |
35 |
Correct |
3 ms |
1260 KB |
Output is correct |
36 |
Correct |
18 ms |
1624 KB |
Output is correct |
37 |
Correct |
92 ms |
2664 KB |
Output is correct |
38 |
Correct |
8 ms |
7000 KB |
Output is correct |
39 |
Correct |
8 ms |
7000 KB |
Output is correct |
40 |
Correct |
10 ms |
7004 KB |
Output is correct |
41 |
Correct |
32 ms |
7208 KB |
Output is correct |
42 |
Correct |
124 ms |
8400 KB |
Output is correct |
43 |
Correct |
204 ms |
115880 KB |
Output is correct |
44 |
Correct |
194 ms |
115864 KB |
Output is correct |
45 |
Correct |
192 ms |
115904 KB |
Output is correct |
46 |
Correct |
238 ms |
116020 KB |
Output is correct |
47 |
Correct |
520 ms |
117440 KB |
Output is correct |
48 |
Correct |
8 ms |
2652 KB |
Output is correct |
49 |
Correct |
42 ms |
2768 KB |
Output is correct |
50 |
Correct |
191 ms |
3336 KB |
Output is correct |
51 |
Correct |
388 ms |
4228 KB |
Output is correct |
52 |
Correct |
63 ms |
23744 KB |
Output is correct |
53 |
Correct |
139 ms |
24068 KB |
Output is correct |
54 |
Correct |
519 ms |
25024 KB |
Output is correct |
55 |
Correct |
905 ms |
25576 KB |
Output is correct |
56 |
Correct |
394 ms |
122668 KB |
Output is correct |
57 |
Correct |
508 ms |
121684 KB |
Output is correct |
58 |
Correct |
1312 ms |
122192 KB |
Output is correct |
59 |
Correct |
2052 ms |
122972 KB |
Output is correct |
60 |
Correct |
815 ms |
252072 KB |
Output is correct |
61 |
Correct |
952 ms |
252096 KB |
Output is correct |
62 |
Correct |
1885 ms |
252004 KB |
Output is correct |
63 |
Correct |
2995 ms |
254196 KB |
Output is correct |
64 |
Execution timed out |
5022 ms |
252136 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |