#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define af(i,a,b) for(int i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod=998244353;
const int maxN=1e5+5;
const ll inf=1e12;
vector<pll> adj[maxN];
ll dist[maxN];
//ll vis[maxN];
ll n,q,w;
vector<vector<ll>> ed;
/*pll dij(ll a){
priority_queue<pll> q;
q.push(MP(0,a));
f(i,1,n+1) dist[i]=0;
f(i,1,n+1) vis[i]=0;
dist[a]=0;
while(!q.empty()){
a=q.top().S;
q.pop();
if(vis[a]==1) continue;
vis[a]=1;
for(auto x:adj[a]){
if(dist[x.F]<dist[a]+x.S){
dist[x.F]=dist[a]+x.S;
q.push(MP(dist[x.F],x.F));
}
}
}
ll res=0,d=-1;
f(i,1,n+1){
if(d<dist[i]){
d=dist[i];
res=i;
}
}
return MP(res,d);
}*/
void dfs(ll a, ll p){
for(auto x:adj[a]){
if(x.F==p) continue;
dist[x.F]=dist[a]+x.S;
dfs(x.F,a);
}
}
ll root(ll a){
f(i,1,n+1) dist[i]=-1;
dist[a]=0;
ll res=0,d=-1;
dfs(a,-1);
f(i,1,n+1){
//cout<<dist[i]<<" ";
if(d<dist[i]){
d=dist[i];
res=i;
}
}
return res;
}
void bin(ll a, ll b){
int x1=ed[a][0];
int x2=ed[a][1];
int beg=0;
int end=adj[x1].size()-1;
int res=-1;
while(beg<=end){
int mid=(beg+end)/2;
if(adj[x1][mid].F<=x2){
res=mid;
beg=mid+1;
}
else end=mid-1;
}
adj[x1][res].S=b;
beg=0;
end=adj[x2].size()-1;
res=-1;
while(beg<=end){
int mid=(beg+end)/2;
if(adj[x2][mid].F<=x1){
res=mid;
beg=mid+1;
}
else end=mid-1;
}
adj[x2][res].S=b;
}
void go(){
ll a,b,c;
cin>>n>>q>>w;
ed.PB({0,0,0});
f(i,0,n-1){
cin>>a>>b>>c;
ed.PB({a,b,c});
adj[a].PB(MP(b,c));
adj[b].PB(MP(a,c));
}
f(i,1,n+1){
sort(adj[i].begin(),adj[i].end());
}
ll last=0;
f(i,0,q){
cin>>a>>b;
a=(a+last)%(n-1)+1;
b=(b+last)%w;
bin(a,b);
ed[a][2]=b;
last=dist[root(root(a))];
cout<<last<<"\n";
}
}
int main(){
fastio;
int test=1;
//cin>>test;
f(i,1,test+1){
//cout<<"Case "<<i<<":\n";
go();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2676 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2680 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2676 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2680 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
76 ms |
2868 KB |
Output is correct |
20 |
Correct |
101 ms |
2848 KB |
Output is correct |
21 |
Correct |
97 ms |
2856 KB |
Output is correct |
22 |
Correct |
114 ms |
2884 KB |
Output is correct |
23 |
Correct |
884 ms |
3412 KB |
Output is correct |
24 |
Correct |
1002 ms |
3424 KB |
Output is correct |
25 |
Correct |
1040 ms |
3444 KB |
Output is correct |
26 |
Correct |
1022 ms |
3552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2680 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
10 ms |
2900 KB |
Output is correct |
5 |
Correct |
45 ms |
3784 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
10 ms |
2696 KB |
Output is correct |
10 |
Correct |
91 ms |
2924 KB |
Output is correct |
11 |
Correct |
445 ms |
3988 KB |
Output is correct |
12 |
Correct |
4 ms |
3412 KB |
Output is correct |
13 |
Correct |
11 ms |
3332 KB |
Output is correct |
14 |
Correct |
102 ms |
3428 KB |
Output is correct |
15 |
Correct |
848 ms |
3628 KB |
Output is correct |
16 |
Correct |
4998 ms |
4800 KB |
Output is correct |
17 |
Correct |
50 ms |
14848 KB |
Output is correct |
18 |
Correct |
229 ms |
14840 KB |
Output is correct |
19 |
Correct |
2093 ms |
14872 KB |
Output is correct |
20 |
Execution timed out |
5022 ms |
15056 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
2824 KB |
Output is correct |
2 |
Correct |
101 ms |
2924 KB |
Output is correct |
3 |
Correct |
489 ms |
3396 KB |
Output is correct |
4 |
Correct |
1024 ms |
4192 KB |
Output is correct |
5 |
Correct |
114 ms |
3984 KB |
Output is correct |
6 |
Correct |
1054 ms |
4228 KB |
Output is correct |
7 |
Execution timed out |
5047 ms |
4788 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5102 ms |
16332 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2676 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2680 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
76 ms |
2868 KB |
Output is correct |
20 |
Correct |
101 ms |
2848 KB |
Output is correct |
21 |
Correct |
97 ms |
2856 KB |
Output is correct |
22 |
Correct |
114 ms |
2884 KB |
Output is correct |
23 |
Correct |
884 ms |
3412 KB |
Output is correct |
24 |
Correct |
1002 ms |
3424 KB |
Output is correct |
25 |
Correct |
1040 ms |
3444 KB |
Output is correct |
26 |
Correct |
1022 ms |
3552 KB |
Output is correct |
27 |
Correct |
1 ms |
2680 KB |
Output is correct |
28 |
Correct |
1 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
30 |
Correct |
10 ms |
2900 KB |
Output is correct |
31 |
Correct |
45 ms |
3784 KB |
Output is correct |
32 |
Correct |
1 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
10 ms |
2696 KB |
Output is correct |
36 |
Correct |
91 ms |
2924 KB |
Output is correct |
37 |
Correct |
445 ms |
3988 KB |
Output is correct |
38 |
Correct |
4 ms |
3412 KB |
Output is correct |
39 |
Correct |
11 ms |
3332 KB |
Output is correct |
40 |
Correct |
102 ms |
3428 KB |
Output is correct |
41 |
Correct |
848 ms |
3628 KB |
Output is correct |
42 |
Correct |
4998 ms |
4800 KB |
Output is correct |
43 |
Correct |
50 ms |
14848 KB |
Output is correct |
44 |
Correct |
229 ms |
14840 KB |
Output is correct |
45 |
Correct |
2093 ms |
14872 KB |
Output is correct |
46 |
Execution timed out |
5022 ms |
15056 KB |
Time limit exceeded |
47 |
Halted |
0 ms |
0 KB |
- |