#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
const int nax = 1e5 + 4;
int n, q;
ll W;
vector<pii> adj[nax];
ll weig[nax];
void solve()
{
cin >> n >> q >> W;
for(int i = 1 ; i < n ;i ++)
{
int a, b;
ll w;
cin >> a >> b >> w;
weig[i] = w;
adj[a].pb({b, i});
adj[b].pb({a, i});
}
ll last = 0ll;
while(q --)
{
ll d, e;
cin >> d >> e;
d = (d + last)%(n - 1);
e = (e + last)%W;
d++;
weig[d] = e;
queue<pll> q;
q.push({1, 0});
pll maxi = {0, 1};\
bool vis[n + 1];
memset(vis, 0, sizeof(vis));
while(!q.empty())
{
int node = q.front().ff;
vis[node] = 1;
ll dis = q.front().ss;
q.pop();
maxi = max(maxi, {dis, node});
for(auto u: adj[node])
{
int nei = u.ff;
int idx = u.ss;
if(vis[nei])
continue;
q.push({nei, dis+ weig[idx]});
}
}
memset(vis, false, sizeof(vis));
q.push({maxi.ss, 0});
//cout << maxi.ss << ' ';
while(!q.empty())
{
int node = q.front().ff;
ll dis = q.front().ss;
q.pop();
vis[node] = 1;
maxi= max(maxi, {dis, node});
for(auto u: adj[node])
{
int nei = u.ff;
int idx = u.ss;
if(vis[nei])
continue;
q.push({nei, dis + weig[idx]});
}
}
cout << maxi.ff << '\n';
last = maxi.ff;
}
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt = 1;
while(tt -- )
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2672 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
3 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2776 KB |
Output is correct |
11 |
Correct |
2 ms |
2676 KB |
Output is correct |
12 |
Correct |
2 ms |
2676 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2676 KB |
Output is correct |
15 |
Correct |
2 ms |
2652 KB |
Output is correct |
16 |
Correct |
2 ms |
2672 KB |
Output is correct |
17 |
Correct |
2 ms |
2552 KB |
Output is correct |
18 |
Correct |
2 ms |
2680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2672 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
3 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2776 KB |
Output is correct |
11 |
Correct |
2 ms |
2676 KB |
Output is correct |
12 |
Correct |
2 ms |
2676 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2676 KB |
Output is correct |
15 |
Correct |
2 ms |
2652 KB |
Output is correct |
16 |
Correct |
2 ms |
2672 KB |
Output is correct |
17 |
Correct |
2 ms |
2552 KB |
Output is correct |
18 |
Correct |
2 ms |
2680 KB |
Output is correct |
19 |
Correct |
150 ms |
2788 KB |
Output is correct |
20 |
Correct |
163 ms |
2772 KB |
Output is correct |
21 |
Correct |
137 ms |
2900 KB |
Output is correct |
22 |
Correct |
219 ms |
2792 KB |
Output is correct |
23 |
Correct |
1104 ms |
3176 KB |
Output is correct |
24 |
Correct |
1051 ms |
3020 KB |
Output is correct |
25 |
Correct |
1053 ms |
3036 KB |
Output is correct |
26 |
Correct |
1754 ms |
3020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
3 ms |
2644 KB |
Output is correct |
4 |
Correct |
22 ms |
2808 KB |
Output is correct |
5 |
Correct |
88 ms |
3788 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
6 ms |
2644 KB |
Output is correct |
9 |
Correct |
34 ms |
2728 KB |
Output is correct |
10 |
Correct |
320 ms |
2940 KB |
Output is correct |
11 |
Correct |
1593 ms |
4120 KB |
Output is correct |
12 |
Correct |
7 ms |
3028 KB |
Output is correct |
13 |
Correct |
36 ms |
3052 KB |
Output is correct |
14 |
Correct |
333 ms |
3180 KB |
Output is correct |
15 |
Correct |
3231 ms |
3544 KB |
Output is correct |
16 |
Execution timed out |
5050 ms |
3756 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
2644 KB |
Output is correct |
2 |
Correct |
282 ms |
2972 KB |
Output is correct |
3 |
Correct |
1338 ms |
3328 KB |
Output is correct |
4 |
Correct |
2685 ms |
4144 KB |
Output is correct |
5 |
Correct |
291 ms |
3376 KB |
Output is correct |
6 |
Correct |
2689 ms |
3596 KB |
Output is correct |
7 |
Execution timed out |
5056 ms |
3940 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5039 ms |
9528 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2672 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2672 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
3 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2776 KB |
Output is correct |
11 |
Correct |
2 ms |
2676 KB |
Output is correct |
12 |
Correct |
2 ms |
2676 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2676 KB |
Output is correct |
15 |
Correct |
2 ms |
2652 KB |
Output is correct |
16 |
Correct |
2 ms |
2672 KB |
Output is correct |
17 |
Correct |
2 ms |
2552 KB |
Output is correct |
18 |
Correct |
2 ms |
2680 KB |
Output is correct |
19 |
Correct |
150 ms |
2788 KB |
Output is correct |
20 |
Correct |
163 ms |
2772 KB |
Output is correct |
21 |
Correct |
137 ms |
2900 KB |
Output is correct |
22 |
Correct |
219 ms |
2792 KB |
Output is correct |
23 |
Correct |
1104 ms |
3176 KB |
Output is correct |
24 |
Correct |
1051 ms |
3020 KB |
Output is correct |
25 |
Correct |
1053 ms |
3036 KB |
Output is correct |
26 |
Correct |
1754 ms |
3020 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
3 ms |
2644 KB |
Output is correct |
30 |
Correct |
22 ms |
2808 KB |
Output is correct |
31 |
Correct |
88 ms |
3788 KB |
Output is correct |
32 |
Correct |
2 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
6 ms |
2644 KB |
Output is correct |
35 |
Correct |
34 ms |
2728 KB |
Output is correct |
36 |
Correct |
320 ms |
2940 KB |
Output is correct |
37 |
Correct |
1593 ms |
4120 KB |
Output is correct |
38 |
Correct |
7 ms |
3028 KB |
Output is correct |
39 |
Correct |
36 ms |
3052 KB |
Output is correct |
40 |
Correct |
333 ms |
3180 KB |
Output is correct |
41 |
Correct |
3231 ms |
3544 KB |
Output is correct |
42 |
Execution timed out |
5050 ms |
3756 KB |
Time limit exceeded |
43 |
Halted |
0 ms |
0 KB |
- |