#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,h[1100000],ans,qu,len[1100000],dia[1100000],dep[1100000],par[1100000];
vector<pair<ll,ll>> v[1100000];
pair<ll,ll> pq;
multiset<ll> st;
pair<ll,pair<ll,ll>> p[1100000],q[1100000];
ll f(ll x,ll y)
{
dep[x]=dep[y]+1;
par[x]=y;
ll i,s=0,z,t=0;
for(i=0;i<h[x];i++)
{
if(v[x][i].first==y)
continue;
z=f(v[x][i].first,x)+v[x][i].second;
s+=z;
t=max(t,z);
}
dia[x]=s;
st.insert(-dia[x]);
len[x]=t;
return t;
}
void g(ll x,ll y)
{
if(x==0)
return;
ll i,s=0,z,t=0;
for(i=0;i<h[x];i++)
{
if(v[x][i].first==y)
continue;
z=len[v[x][i].first]+v[x][i].second;
s+=z;
t=max(t,z);
}
st.erase(st.find(-dia[x]));
dia[x]=s;
st.insert(-dia[x]);
len[x]=t;
g(par[x],par[y]);
return;
}
int main()
{
scanf("%lld %lld %lld",&n,&qu,&w);
for(i=1;i<n;i++)
{
scanf("%lld %lld %lld",&x,&y,&z);
p[i]={x,{h[x],z}};
q[i]={y,{h[y],z}};
v[x].push_back({y,z});
v[y].push_back({x,z});
h[x]++;
h[y]++;
}
f(1,0);
for(i=1;i<=qu;i++)
{
scanf("%lld %lld",&x,&y);
x=(x+ans)%(n-1);
y=(y+ans)%w;
x++;
v[p[x].first][p[x].second.first].second=y;
p[x].second.second=y;
v[q[x].first][q[x].second.first].second=y;
q[x].second.second=y;
y=p[x].first;
x=q[x].first;
if(dep[x]<dep[y])
swap(x,y);
g(x,y);
ans=(*st.begin());
ans*=-1;
printf("%lld\n",ans);
}
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%lld %lld %lld",&n,&qu,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%lld %lld %lld",&x,&y,&z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%lld %lld",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
35164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
35164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
35164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
35472 KB |
Output is correct |
2 |
Correct |
18 ms |
35504 KB |
Output is correct |
3 |
Correct |
56 ms |
35600 KB |
Output is correct |
4 |
Correct |
100 ms |
35924 KB |
Output is correct |
5 |
Correct |
16 ms |
38492 KB |
Output is correct |
6 |
Correct |
29 ms |
38688 KB |
Output is correct |
7 |
Correct |
85 ms |
38856 KB |
Output is correct |
8 |
Correct |
169 ms |
40348 KB |
Output is correct |
9 |
Correct |
40 ms |
47696 KB |
Output is correct |
10 |
Correct |
59 ms |
47696 KB |
Output is correct |
11 |
Correct |
141 ms |
48504 KB |
Output is correct |
12 |
Correct |
252 ms |
49256 KB |
Output is correct |
13 |
Correct |
74 ms |
57684 KB |
Output is correct |
14 |
Correct |
103 ms |
58112 KB |
Output is correct |
15 |
Correct |
210 ms |
58656 KB |
Output is correct |
16 |
Correct |
313 ms |
59216 KB |
Output is correct |
17 |
Correct |
708 ms |
58944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5039 ms |
56400 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
35164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |