Submission #944008

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
944008	2024-03-12T06:31:27 Z	Minbaev	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	219 ms	18716 KB

diameter

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define int long long
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int N=3e5 + 5	;
const int inf = 1e17 + 7;
const int mod = 998244353;

int n,m,k;
vector<pii>g[N];

pii t[N*4];

void update(int tl, int tr, int v, int pos, int val){
	
	if(tl == tr){
		t[v] = {val,0};
		return;
	}
	int tm = (tl + tr)/2;
	
	if(pos<=tm)
		update(tl,tm,v*2,pos,val);
	else 
		update(tm+1,tr,v*2+1,pos,val);
	
	vector<int>a = {t[v*2].f, t[v*2].s, t[v*2+1].f, t[v*2+1].s};
	sort(rall(a));
	
	t[v] = {a[0],a[1]};
}

void solve(){
	
	cin >> n >> m >> k;
	
	
	for(int i = 0;i<n - 1;i++){
		int a,b,c;
		cin >> a >> b >> c;
		
		g[a].pb({b,c});
		g[b].pb({a,c});
		update(0,n-2,1,i,c);
	}
	
	int last = 0;
	
	while(m--){
		int a,b;
		
		cin >> a >> b;
		
		int pos = (a + last) % (n - 1);
		int val = (b + last) % k;
		
		update(0,n-2,1,pos,val);
		cout<<t[1].f + t[1].s<<"\n";
		
		last = t[1].f + t[1].s;
	}	
	
	
	
}

signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt>>n;
	while(tt--)solve();

}

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	7516 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	7516 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	7512 KB	Output is correct
2	Correct	2 ms	7516 KB	Output is correct
3	Correct	3 ms	7516 KB	Output is correct
4	Correct	9 ms	7516 KB	Output is correct
5	Correct	45 ms	8016 KB	Output is correct
6	Correct	2 ms	7516 KB	Output is correct
7	Correct	2 ms	7516 KB	Output is correct
8	Correct	2 ms	7516 KB	Output is correct
9	Correct	3 ms	7516 KB	Output is correct
10	Correct	13 ms	7784 KB	Output is correct
11	Correct	57 ms	8012 KB	Output is correct
12	Correct	5 ms	10076 KB	Output is correct
13	Correct	8 ms	10076 KB	Output is correct
14	Correct	9 ms	10076 KB	Output is correct
15	Correct	19 ms	10072 KB	Output is correct
16	Correct	77 ms	10636 KB	Output is correct
17	Correct	71 ms	16576 KB	Output is correct
18	Correct	78 ms	16548 KB	Output is correct
19	Correct	74 ms	16560 KB	Output is correct
20	Correct	89 ms	16496 KB	Output is correct
21	Correct	167 ms	17176 KB	Output is correct