/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
void fastscan(int& number)
{
//variable to indicate sign of input number
bool negative = false;
register int c;
number = 0;
// extract current character from buffer
c = getchar();
while (c == 10)
c = getchar();
if (c == '-')
{
// number is negative
negative = true;
// extract the next character from the buffer
c = getchar();
}
// Keep on extracting characters if they are integers
// i.e ASCII Value lies from '0'(48) to '9' (57)
for (; (c > 47 && c < 58); c = getchar())
number = number * 10 + c - 48;
// if scanned input has a negative sign, negate the
// value of the input number
if (negative)
number *= -1;
}
struct segtree
{
vector<LL> d;
vector<pair<LL, int>> t;
void build(int v, int l, int r, vector<int>& a, vector<LL>& D, unordered_map<int, int>& b)
{
if (l == r)
{
t[v].first = D[a[l]];
t[v].second = b[a[l]];
d[v] = 0;
return;
}
int m = (l + r) / 2;
build(v * 2, l, m, a, D, b);
build(v * 2 + 1, m + 1, r, a, D, b);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
segtree(int n = 0)
{
t.resize(n * 4 + 5);
d.resize(n * 4 + 5);
}
segtree(vector<int>& a, vector<LL>& D, unordered_map<int, int>& b)
{
t.resize(a.size() * 4 + 5);
d.resize(a.size() * 4 + 5);
build(1, 0, a.size() - 1, a, D, b);
}
void push(int v, int l, int r, int f = 1)
{
if (d[v] == 0)
return;
if (l != r)
{
int m = (l + r) / 2;
d[v * 2] += d[v];
d[v * 2 + 1] += d[v];
if (f)
{
push(v * 2, l, m, 0);
push(v * 2 + 1, m + 1, r, 0);
}
}
t[v].first += d[v];
d[v] = 0;
}
pair<LL, int> get(int v, int l, int r, int i, int j)
{
push(v, l, r);
if (i > j)
return MP(0, 0);
if (l == i && r == j)
return t[v];
int m = (l + r) / 2;
return max(
get(v * 2, l, m, i, min(j, m)),
get(v * 2 + 1, m + 1, r, max(i, m + 1), j)
);
}
void add(int v, int l, int r, int i, int j, LL val)
{
push(v, l, r);
if (i > j)
return;
if (l == i && r == j)
{
d[v] += val;
push(v, l, r);
return;
}
int m = (l + r) / 2;
add(v * 2, l, m, i, min(j, m), val);
add(v * 2 + 1, m + 1, r, max(i, m + 1), j, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
};
LL n, q;
LL W, w[100005], sz[100005], used[100005], color[100005], col, ans;
vector<LL> d(100005);
vector<pair<int, int>> g[100005];
vector<int> ord[100005];
segtree seg[100005];
unordered_map<int, int> subtree[100005], tin[100005], tout[100005], pos[100005], centr[100005];
multiset<LL> best;
void dfsSize(int v, int p)
{
color[v] = col;
sz[v] = 1;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
if (used[to] || to == p)
continue;
dfsSize(to, v);
sz[v] += sz[to];
}
}
int centroid(int v)
{
col++;
dfsSize(v, 0);
col++;
queue<int> q;
q.push(v);
while (!q.empty())
{
int x = q.front();
q.pop();
color[x] = col;
bool is = (sz[v] >= (sz[v] - sz[x]) * 2);
for (int i = 0; i < g[x].size(); i++)
{
int to = g[x][i].first;
if (color[to] == col || used[to])
continue;
q.push(to);
is &= (sz[v] >= sz[to] * 2);
}
if (is)
return x;
}
}
void dfs(int Centr, int Sub, int v, int p, LL dist)
{
d[v] = dist;
subtree[Centr][v] = Sub;
ord[Centr].PB(v);
tin[Centr][v] = ord[Centr].size() - 1;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
int d = g[v][i].second;
if (to == p || used[to])
continue;
pos[Centr][d] = to;
dfs(Centr, Sub, to, v, dist + w[d]);
}
tout[Centr][v] = ord[Centr].size() - 1;
}
LL getMax(int v)
{
pair<LL, LL> mx1, mx2;
mx1 = seg[v].get(1, 0, ord[v].size() - 1, 0, ord[v].size() - 1);
if (mx1.first == 0)
return 0;
mx2 = max(
seg[v].get(1, 0, ord[v].size() - 1, 0, tin[v][mx1.second] - 1),
seg[v].get(1, 0, ord[v].size() - 1, tout[v][mx1.second] + 1, ord[v].size() - 1)
);
return mx1.first + mx2.first;
}
void calc(int v)
{
used[v] = 1;
ord[v].PB(v);
tin[v][v] = ord[v].size() - 1;
d[v] = 0;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
int d = g[v][i].second;
if (used[to])
continue;
pos[v][d] = to;
dfs(v, to, to, v, w[d]);
}
tout[v][v] = ord[v].size() - 1;
seg[v] = segtree(ord[v], d, subtree[v]);
LL mx = getMax(v);
//cout<<"!!!"<<v<<" > "<<mx<<endl;
best.insert(mx);
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
if (used[to])
continue;
calc(centr[v][to] = centroid(to));
}
}
void solve(int v, int P, LL val)
{
if (pos[v].find(P) == pos[v].end())
return;
int p = pos[v][P];
LL mx;
mx = getMax(v);
//cout<<"!!"<<v<<" > "<<mx<<endl;
best.erase(best.find(mx));
seg[v].add(1, 0, ord[v].size() - 1, tin[v][p], tout[v][p], val);
mx = getMax(v);
//cout<<"!"<<v<<" > "<<mx<<endl;
best.insert(mx);
solve(centr[v][subtree[v][p]], P, val);
}
int main()
{
cin >> n >> q >> W;
for (int i = 1; i <= n - 1; i++)
{
int a, b,ww;
fastscan(a);
fastscan(b);
fastscan(ww);
w[i] = ww;
g[a].PB(MP(b, i));
g[b].PB(MP(a, i));
}
calc(centr[0][1] = centroid(1));
while (q--)
{
int p;
int D;
fastscan(p);
fastscan(D);
p = (p + ans) % (n - 1);
D = (D + ans) % W;
p++;
solve(centr[0][1], p, D - w[p]);
w[p] = D;
if (!best.empty())
{
auto it = best.end();
--it;
ans = (*it);
}
else
ans = 0;
printf("%lld\n", ans);
}
return 0;
}
/*
7 1 1000
1 2 10
2 3 1
2 4 1
1 5 1
5 6 1
5 7 1
0 1
*/
Compilation message
diameter.cpp: In function 'void fastscan(int&)':
diameter.cpp:30:15: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
register int c;
^
diameter.cpp: In function 'void dfsSize(int, int)':
diameter.cpp:155:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
diameter.cpp: In function 'int centroid(int)':
diameter.cpp:178:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[x].size(); i++)
~~^~~~~~~~~~~~~
diameter.cpp: In function 'void dfs(int, int, int, int, long long int)':
diameter.cpp:199:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
diameter.cpp: In function 'void calc(int)':
diameter.cpp:233:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
diameter.cpp:250:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
diameter.cpp: In function 'int centroid(int)':
diameter.cpp:190:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
51960 KB |
Output is correct |
2 |
Correct |
49 ms |
51960 KB |
Output is correct |
3 |
Correct |
44 ms |
52088 KB |
Output is correct |
4 |
Correct |
45 ms |
52088 KB |
Output is correct |
5 |
Correct |
45 ms |
51960 KB |
Output is correct |
6 |
Correct |
46 ms |
51960 KB |
Output is correct |
7 |
Correct |
43 ms |
52088 KB |
Output is correct |
8 |
Correct |
44 ms |
52088 KB |
Output is correct |
9 |
Correct |
46 ms |
52088 KB |
Output is correct |
10 |
Correct |
47 ms |
52088 KB |
Output is correct |
11 |
Correct |
45 ms |
52088 KB |
Output is correct |
12 |
Correct |
45 ms |
52088 KB |
Output is correct |
13 |
Correct |
45 ms |
52088 KB |
Output is correct |
14 |
Correct |
45 ms |
52216 KB |
Output is correct |
15 |
Correct |
47 ms |
52216 KB |
Output is correct |
16 |
Correct |
45 ms |
52088 KB |
Output is correct |
17 |
Correct |
45 ms |
52216 KB |
Output is correct |
18 |
Correct |
44 ms |
52216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
51960 KB |
Output is correct |
2 |
Correct |
49 ms |
51960 KB |
Output is correct |
3 |
Correct |
44 ms |
52088 KB |
Output is correct |
4 |
Correct |
45 ms |
52088 KB |
Output is correct |
5 |
Correct |
45 ms |
51960 KB |
Output is correct |
6 |
Correct |
46 ms |
51960 KB |
Output is correct |
7 |
Correct |
43 ms |
52088 KB |
Output is correct |
8 |
Correct |
44 ms |
52088 KB |
Output is correct |
9 |
Correct |
46 ms |
52088 KB |
Output is correct |
10 |
Correct |
47 ms |
52088 KB |
Output is correct |
11 |
Correct |
45 ms |
52088 KB |
Output is correct |
12 |
Correct |
45 ms |
52088 KB |
Output is correct |
13 |
Correct |
45 ms |
52088 KB |
Output is correct |
14 |
Correct |
45 ms |
52216 KB |
Output is correct |
15 |
Correct |
47 ms |
52216 KB |
Output is correct |
16 |
Correct |
45 ms |
52088 KB |
Output is correct |
17 |
Correct |
45 ms |
52216 KB |
Output is correct |
18 |
Correct |
44 ms |
52216 KB |
Output is correct |
19 |
Correct |
85 ms |
53880 KB |
Output is correct |
20 |
Correct |
95 ms |
54268 KB |
Output is correct |
21 |
Correct |
94 ms |
54392 KB |
Output is correct |
22 |
Correct |
104 ms |
54780 KB |
Output is correct |
23 |
Correct |
156 ms |
62456 KB |
Output is correct |
24 |
Correct |
196 ms |
65272 KB |
Output is correct |
25 |
Correct |
211 ms |
66424 KB |
Output is correct |
26 |
Correct |
217 ms |
68856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
51960 KB |
Output is correct |
2 |
Correct |
45 ms |
52088 KB |
Output is correct |
3 |
Correct |
47 ms |
52088 KB |
Output is correct |
4 |
Correct |
58 ms |
52216 KB |
Output is correct |
5 |
Correct |
112 ms |
53240 KB |
Output is correct |
6 |
Correct |
44 ms |
51960 KB |
Output is correct |
7 |
Correct |
48 ms |
52600 KB |
Output is correct |
8 |
Correct |
46 ms |
52344 KB |
Output is correct |
9 |
Correct |
47 ms |
52416 KB |
Output is correct |
10 |
Correct |
69 ms |
52600 KB |
Output is correct |
11 |
Correct |
163 ms |
53752 KB |
Output is correct |
12 |
Correct |
61 ms |
55800 KB |
Output is correct |
13 |
Correct |
62 ms |
55800 KB |
Output is correct |
14 |
Correct |
65 ms |
55800 KB |
Output is correct |
15 |
Correct |
94 ms |
56056 KB |
Output is correct |
16 |
Correct |
225 ms |
57208 KB |
Output is correct |
17 |
Correct |
336 ms |
126060 KB |
Output is correct |
18 |
Correct |
341 ms |
126064 KB |
Output is correct |
19 |
Correct |
336 ms |
126188 KB |
Output is correct |
20 |
Correct |
390 ms |
126316 KB |
Output is correct |
21 |
Correct |
652 ms |
126956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
54392 KB |
Output is correct |
2 |
Correct |
106 ms |
54520 KB |
Output is correct |
3 |
Correct |
282 ms |
55032 KB |
Output is correct |
4 |
Correct |
510 ms |
55928 KB |
Output is correct |
5 |
Correct |
185 ms |
84856 KB |
Output is correct |
6 |
Correct |
293 ms |
85112 KB |
Output is correct |
7 |
Correct |
759 ms |
85624 KB |
Output is correct |
8 |
Correct |
1367 ms |
86496 KB |
Output is correct |
9 |
Correct |
842 ms |
248068 KB |
Output is correct |
10 |
Correct |
1026 ms |
248068 KB |
Output is correct |
11 |
Correct |
1862 ms |
248708 KB |
Output is correct |
12 |
Correct |
2887 ms |
248912 KB |
Output is correct |
13 |
Correct |
1764 ms |
470044 KB |
Output is correct |
14 |
Correct |
1979 ms |
470060 KB |
Output is correct |
15 |
Correct |
3057 ms |
470404 KB |
Output is correct |
16 |
Correct |
4295 ms |
470792 KB |
Output is correct |
17 |
Execution timed out |
5057 ms |
470544 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5067 ms |
367280 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
51960 KB |
Output is correct |
2 |
Correct |
49 ms |
51960 KB |
Output is correct |
3 |
Correct |
44 ms |
52088 KB |
Output is correct |
4 |
Correct |
45 ms |
52088 KB |
Output is correct |
5 |
Correct |
45 ms |
51960 KB |
Output is correct |
6 |
Correct |
46 ms |
51960 KB |
Output is correct |
7 |
Correct |
43 ms |
52088 KB |
Output is correct |
8 |
Correct |
44 ms |
52088 KB |
Output is correct |
9 |
Correct |
46 ms |
52088 KB |
Output is correct |
10 |
Correct |
47 ms |
52088 KB |
Output is correct |
11 |
Correct |
45 ms |
52088 KB |
Output is correct |
12 |
Correct |
45 ms |
52088 KB |
Output is correct |
13 |
Correct |
45 ms |
52088 KB |
Output is correct |
14 |
Correct |
45 ms |
52216 KB |
Output is correct |
15 |
Correct |
47 ms |
52216 KB |
Output is correct |
16 |
Correct |
45 ms |
52088 KB |
Output is correct |
17 |
Correct |
45 ms |
52216 KB |
Output is correct |
18 |
Correct |
44 ms |
52216 KB |
Output is correct |
19 |
Correct |
85 ms |
53880 KB |
Output is correct |
20 |
Correct |
95 ms |
54268 KB |
Output is correct |
21 |
Correct |
94 ms |
54392 KB |
Output is correct |
22 |
Correct |
104 ms |
54780 KB |
Output is correct |
23 |
Correct |
156 ms |
62456 KB |
Output is correct |
24 |
Correct |
196 ms |
65272 KB |
Output is correct |
25 |
Correct |
211 ms |
66424 KB |
Output is correct |
26 |
Correct |
217 ms |
68856 KB |
Output is correct |
27 |
Correct |
49 ms |
51960 KB |
Output is correct |
28 |
Correct |
45 ms |
52088 KB |
Output is correct |
29 |
Correct |
47 ms |
52088 KB |
Output is correct |
30 |
Correct |
58 ms |
52216 KB |
Output is correct |
31 |
Correct |
112 ms |
53240 KB |
Output is correct |
32 |
Correct |
44 ms |
51960 KB |
Output is correct |
33 |
Correct |
48 ms |
52600 KB |
Output is correct |
34 |
Correct |
46 ms |
52344 KB |
Output is correct |
35 |
Correct |
47 ms |
52416 KB |
Output is correct |
36 |
Correct |
69 ms |
52600 KB |
Output is correct |
37 |
Correct |
163 ms |
53752 KB |
Output is correct |
38 |
Correct |
61 ms |
55800 KB |
Output is correct |
39 |
Correct |
62 ms |
55800 KB |
Output is correct |
40 |
Correct |
65 ms |
55800 KB |
Output is correct |
41 |
Correct |
94 ms |
56056 KB |
Output is correct |
42 |
Correct |
225 ms |
57208 KB |
Output is correct |
43 |
Correct |
336 ms |
126060 KB |
Output is correct |
44 |
Correct |
341 ms |
126064 KB |
Output is correct |
45 |
Correct |
336 ms |
126188 KB |
Output is correct |
46 |
Correct |
390 ms |
126316 KB |
Output is correct |
47 |
Correct |
652 ms |
126956 KB |
Output is correct |
48 |
Correct |
62 ms |
54392 KB |
Output is correct |
49 |
Correct |
106 ms |
54520 KB |
Output is correct |
50 |
Correct |
282 ms |
55032 KB |
Output is correct |
51 |
Correct |
510 ms |
55928 KB |
Output is correct |
52 |
Correct |
185 ms |
84856 KB |
Output is correct |
53 |
Correct |
293 ms |
85112 KB |
Output is correct |
54 |
Correct |
759 ms |
85624 KB |
Output is correct |
55 |
Correct |
1367 ms |
86496 KB |
Output is correct |
56 |
Correct |
842 ms |
248068 KB |
Output is correct |
57 |
Correct |
1026 ms |
248068 KB |
Output is correct |
58 |
Correct |
1862 ms |
248708 KB |
Output is correct |
59 |
Correct |
2887 ms |
248912 KB |
Output is correct |
60 |
Correct |
1764 ms |
470044 KB |
Output is correct |
61 |
Correct |
1979 ms |
470060 KB |
Output is correct |
62 |
Correct |
3057 ms |
470404 KB |
Output is correct |
63 |
Correct |
4295 ms |
470792 KB |
Output is correct |
64 |
Execution timed out |
5057 ms |
470544 KB |
Time limit exceeded |