#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);
const ll N = 100010;
vector<pair<int, ll>> v[N];
int n;
pair<ll, ll> Dfs(int g, int p)
{
ll maher = 0, ind = g;
for (auto to : v[g])
{
if (to.first != p)
{
pair<ll, ll> x = Dfs(to.first, g);
if (to.second + x.second >= maher)
{
maher = to.second + x.second;
ind = x.first;
}
}
}
return { ind, maher };
}
ll get_diam()
{
return Dfs(Dfs(1, -1).first, -1).second;
}
vector<ll> karuc;
int tin[N], tout[N], ti = 0;
pair<int, int> s[8 * N];
void build(int p, int lp, int rp)
{
if (lp == rp)
{
s[p] = { karuc[lp], 0 };
return;
}
int m = (lp + rp) / 2;
build(p * 2, lp, m);
build(p * 2 + 1, m + 1, rp);
s[p].first = max(s[p * 2].first, s[p * 2 + 1].first);
if (s[p].first == s[p * 2].first)
s[p].second = max(s[p * 2].second, s[p * 2 + 1].first);
else
s[p].second = max(s[p * 2].first, s[p * 2 + 1].second);
}
void Dfs1(int g, int p, ll her)
{
karuc.push_back(her);
tin[g] = ti++;
for (auto to : v[g])
{
if (to.first != p)
{
Dfs1(to.first, g, her + to.second);
}
}
tout[g] = ti++;
karuc.push_back(her);
}
bool papaya(int a, int b)
{
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
ll ly[8 * N];
void push(int p)
{
ly[p * 2] += ly[p];
ly[p * 2 + 1] += ly[p];
s[p * 2].first = max(s[p * 2].first + ly[p], 0LL);
s[p * 2].second = max(s[p * 2].second + ly[p], 0LL);
s[p * 2 + 1].first = max(s[p * 2 + 1].first + ly[p], 0LL);
s[p * 2 + 1].second = max(s[p * 2 + 1].second + ly[p], 0LL);
ly[p] = 0;
}
void update(int p, int lp, int rp, int l, int r, ll pox)
{
if (l > r)
return;
if (lp == l && rp == r)
{
s[p].first = max(s[p].first + pox, 0LL);
s[p].second = max(s[p].second + pox, 0LL);
ly[p] += pox;
return;
}
push(p);
int m = (lp + rp) / 2;
update(p * 2, lp, m, l, min(m, r), pox);
update(p * 2 + 1, m + 1, rp, max(l, m + 1), r, pox);
s[p].first = max(s[p * 2].first, s[p * 2 + 1].first);
if (s[p].first == s[p * 2].first)
s[p].second = max(s[p * 2].second, s[p * 2 + 1].first);
else
s[p].second = max(s[p * 2].first, s[p * 2 + 1].second);
}
void solve()
{
ll q, w, i, j, x, y, z;
cin >> n >> q >> w;
if (n <= 5000 && q <= 5000 && w <= 10000)
{
vector<pair<ll, ll>> kox;
for (i = 0; i < n - 1; i++)
{
cin >> x >> y >> z;
kox.push_back({ x, y });
v[x].push_back({ y, z });
v[y].push_back({ x, z });
}
for (i = 0; i <= n; i++)
{
sort(v[i].begin(), v[i].end());
}
ll last = 0;
for (i = 0; i < q; i++)
{
cin >> x >> y;
x = (x + last) % (n - 1);
y = (y + last) % w;
int x1 = kox[x].first;
int y1 = kox[x].second;
v[x1][lower_bound(v[x1].begin(), v[x1].end(), make_pair(y1, 0LL)) - v[x1].begin()].second = y;
v[y1][lower_bound(v[y1].begin(), v[y1].end(), make_pair(x1, 0LL)) - v[y1].begin()].second = y;
last = get_diam();
cout << last << '\n';
}
return;
}
vector<pair<ll, pair<ll, ll>>> kox;
multiset<ll> se;
int st = 1;
for (i = 0; i < n - 1; i++)
{
cin >> x >> y >> z;
if (x != 1 && y != 1)
st = 0;
kox.push_back({ z, {x, y} });
v[x].push_back({ y, z });
v[y].push_back({ x, z });
se.insert(z);
}
//st = 0;////////
if (st)
{
ll last = 0;
for (i = 0; i < q; i++)
{
cin >> x >> y;
x = (x + last) % (n - 1);
y = (y + last) % w;
int x1 = kox[x].second.first;
int y1 = kox[x].second.second;
se.erase(se.find(kox[x].first));
se.insert(y);
kox[x].first = y;
last = *--se.end();
if (se.size() != 1)
last += *----se.end();
cout << last << '\n';
}
return;
}
Dfs1(1, -1, 0);
build(1, 0, ti - 1);//
ll last = 0;
for (i = 0; i < q; i++)
{
cin >> x >> y;
x = (x + last) % (n - 1);
y = (y + last) % w;
int x1 = kox[x].second.first;
int y1 = kox[x].second.second;
int poxgag = x1;
if (papaya(x1, y1))
{
poxgag = y1;
}
update(1, 0, ti - 1, tin[poxgag], tout[poxgag], y - kox[x].first);
kox[x].first = y;
last = s[1].first + s[1].second;
cout << last << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Compilation message
diameter.cpp: In function 'void solve()':
diameter.cpp:188:17: warning: unused variable 'x1' [-Wunused-variable]
188 | int x1 = kox[x].second.first;
| ^~
diameter.cpp:189:17: warning: unused variable 'y1' [-Wunused-variable]
189 | int y1 = kox[x].second.second;
| ^~
diameter.cpp:135:17: warning: unused variable 'j' [-Wunused-variable]
135 | ll q, w, i, j, x, y, z;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
2 ms |
3420 KB |
Output is correct |
4 |
Correct |
2 ms |
3420 KB |
Output is correct |
5 |
Correct |
2 ms |
3420 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
8 |
Correct |
2 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
3420 KB |
Output is correct |
10 |
Correct |
2 ms |
3420 KB |
Output is correct |
11 |
Correct |
2 ms |
3420 KB |
Output is correct |
12 |
Correct |
2 ms |
3420 KB |
Output is correct |
13 |
Correct |
1 ms |
3420 KB |
Output is correct |
14 |
Correct |
1 ms |
3420 KB |
Output is correct |
15 |
Correct |
1 ms |
3420 KB |
Output is correct |
16 |
Correct |
2 ms |
3420 KB |
Output is correct |
17 |
Correct |
2 ms |
3672 KB |
Output is correct |
18 |
Correct |
2 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
2 ms |
3420 KB |
Output is correct |
4 |
Correct |
2 ms |
3420 KB |
Output is correct |
5 |
Correct |
2 ms |
3420 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
8 |
Correct |
2 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
3420 KB |
Output is correct |
10 |
Correct |
2 ms |
3420 KB |
Output is correct |
11 |
Correct |
2 ms |
3420 KB |
Output is correct |
12 |
Correct |
2 ms |
3420 KB |
Output is correct |
13 |
Correct |
1 ms |
3420 KB |
Output is correct |
14 |
Correct |
1 ms |
3420 KB |
Output is correct |
15 |
Correct |
1 ms |
3420 KB |
Output is correct |
16 |
Correct |
2 ms |
3420 KB |
Output is correct |
17 |
Correct |
2 ms |
3672 KB |
Output is correct |
18 |
Correct |
2 ms |
3420 KB |
Output is correct |
19 |
Correct |
60 ms |
3676 KB |
Output is correct |
20 |
Correct |
65 ms |
3768 KB |
Output is correct |
21 |
Correct |
71 ms |
3772 KB |
Output is correct |
22 |
Correct |
103 ms |
3860 KB |
Output is correct |
23 |
Correct |
609 ms |
4188 KB |
Output is correct |
24 |
Correct |
743 ms |
4396 KB |
Output is correct |
25 |
Correct |
870 ms |
4448 KB |
Output is correct |
26 |
Correct |
1122 ms |
4540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
2 ms |
3420 KB |
Output is correct |
3 |
Correct |
2 ms |
3676 KB |
Output is correct |
4 |
Correct |
7 ms |
3676 KB |
Output is correct |
5 |
Correct |
28 ms |
4724 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
2 ms |
3676 KB |
Output is correct |
8 |
Correct |
2 ms |
3676 KB |
Output is correct |
9 |
Correct |
10 ms |
3676 KB |
Output is correct |
10 |
Correct |
9 ms |
3956 KB |
Output is correct |
11 |
Correct |
32 ms |
4956 KB |
Output is correct |
12 |
Correct |
3 ms |
4188 KB |
Output is correct |
13 |
Correct |
4 ms |
4188 KB |
Output is correct |
14 |
Correct |
4 ms |
4188 KB |
Output is correct |
15 |
Correct |
10 ms |
4444 KB |
Output is correct |
16 |
Correct |
46 ms |
5716 KB |
Output is correct |
17 |
Correct |
52 ms |
16492 KB |
Output is correct |
18 |
Correct |
52 ms |
16496 KB |
Output is correct |
19 |
Correct |
52 ms |
16488 KB |
Output is correct |
20 |
Correct |
69 ms |
16808 KB |
Output is correct |
21 |
Correct |
134 ms |
18412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
3676 KB |
Output is correct |
2 |
Incorrect |
6 ms |
5980 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
108 ms |
58228 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
2 ms |
3420 KB |
Output is correct |
4 |
Correct |
2 ms |
3420 KB |
Output is correct |
5 |
Correct |
2 ms |
3420 KB |
Output is correct |
6 |
Correct |
2 ms |
3420 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
8 |
Correct |
2 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
3420 KB |
Output is correct |
10 |
Correct |
2 ms |
3420 KB |
Output is correct |
11 |
Correct |
2 ms |
3420 KB |
Output is correct |
12 |
Correct |
2 ms |
3420 KB |
Output is correct |
13 |
Correct |
1 ms |
3420 KB |
Output is correct |
14 |
Correct |
1 ms |
3420 KB |
Output is correct |
15 |
Correct |
1 ms |
3420 KB |
Output is correct |
16 |
Correct |
2 ms |
3420 KB |
Output is correct |
17 |
Correct |
2 ms |
3672 KB |
Output is correct |
18 |
Correct |
2 ms |
3420 KB |
Output is correct |
19 |
Correct |
60 ms |
3676 KB |
Output is correct |
20 |
Correct |
65 ms |
3768 KB |
Output is correct |
21 |
Correct |
71 ms |
3772 KB |
Output is correct |
22 |
Correct |
103 ms |
3860 KB |
Output is correct |
23 |
Correct |
609 ms |
4188 KB |
Output is correct |
24 |
Correct |
743 ms |
4396 KB |
Output is correct |
25 |
Correct |
870 ms |
4448 KB |
Output is correct |
26 |
Correct |
1122 ms |
4540 KB |
Output is correct |
27 |
Correct |
1 ms |
3420 KB |
Output is correct |
28 |
Correct |
2 ms |
3420 KB |
Output is correct |
29 |
Correct |
2 ms |
3676 KB |
Output is correct |
30 |
Correct |
7 ms |
3676 KB |
Output is correct |
31 |
Correct |
28 ms |
4724 KB |
Output is correct |
32 |
Correct |
2 ms |
3420 KB |
Output is correct |
33 |
Correct |
2 ms |
3676 KB |
Output is correct |
34 |
Correct |
2 ms |
3676 KB |
Output is correct |
35 |
Correct |
10 ms |
3676 KB |
Output is correct |
36 |
Correct |
9 ms |
3956 KB |
Output is correct |
37 |
Correct |
32 ms |
4956 KB |
Output is correct |
38 |
Correct |
3 ms |
4188 KB |
Output is correct |
39 |
Correct |
4 ms |
4188 KB |
Output is correct |
40 |
Correct |
4 ms |
4188 KB |
Output is correct |
41 |
Correct |
10 ms |
4444 KB |
Output is correct |
42 |
Correct |
46 ms |
5716 KB |
Output is correct |
43 |
Correct |
52 ms |
16492 KB |
Output is correct |
44 |
Correct |
52 ms |
16496 KB |
Output is correct |
45 |
Correct |
52 ms |
16488 KB |
Output is correct |
46 |
Correct |
69 ms |
16808 KB |
Output is correct |
47 |
Correct |
134 ms |
18412 KB |
Output is correct |
48 |
Correct |
12 ms |
3676 KB |
Output is correct |
49 |
Incorrect |
6 ms |
5980 KB |
Output isn't correct |
50 |
Halted |
0 ms |
0 KB |
- |