oj.uz

Submission #967806

# Submission time Handle Problem Language Result Execution time Memory
967806 2024-04-22T20:41:22 Z shadow_sami Dynamic Diameter (CEOI19_diameter) C++17
24 / 100
 223 ms 58612 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
// typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"
 
// ==========================(debug)============================================================================================== //
 
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif
 
void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
 
// ==========================(debug)============================================================================================== //
 
ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;
 
// ==========================(MOD)=============================================================================================== //
 
ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }
 
// ==========================(MOD)=============================================================================================== //
 
bool f = false;
vector<pi> adj[mx];
ll c[mx];
ll dp[mx];
ll to[mx];
ll st[mx];
ll id[mx];
ll en[mx];
ll sr,de;
ll aeh[mx];
ll timer = 0;
 
typedef struct SEGMENT_TREE{
	vi arr;
	vi laz;
	ll range;
	void init(ll k){
		range = 4 * k;
		arr.resize(range);
		laz.resize(range);
		fip(0,range)
			laz[i] = arr[i] = 0;
		return;
	}
	void prop(ll ptr,ll l,ll r){
		if(laz[ptr]){
			arr[ptr] += laz[ptr];
			if(l!=r){
				laz[2*ptr] += laz[ptr];
				laz[2*ptr+1] += laz[ptr];
			}
			laz[ptr] = 0;
		}
		return;
	}
	ll build(ll ptr,ll l,ll r){
		if(l==r){
			arr[ptr] = dp[id[l]];
			return arr[ptr];
		}
		ll mid = l + (r-l) / 2;
		build(2*ptr,l,mid);
		build(2*ptr+1,mid+1,r);
		arr[ptr] = max(arr[2*ptr],arr[2*ptr+1]);
		return arr[ptr];
	}
	ll update(ll ptr,ll l,ll r,ll st,ll en,ll val){
		prop(ptr,l,r);
		if(l>en || r<st)
			return arr[ptr];
		if(l>=st && r<=en){
			laz[ptr] += val;
			prop(ptr,l,r);
			return arr[ptr];
		}
		ll mid = l +(r-l) / 2;
		update(2*ptr,l,mid,st,en,val);
		update(2*ptr+1,mid+1,r,st,en,val);
		arr[ptr] = max(arr[2*ptr],arr[2*ptr+1]);
		return arr[ptr];
	}
	ll query(ll ptr,ll l,ll r,ll st,ll en){
		prop(ptr,l,r);
		if(l>en || r<st)
			return -1e18;
		if(l>=st && r<=en)
			return arr[ptr];
		ll mid = l +(r-l) / 2;
		return max(query(2*ptr,l,mid,st,en),query(2*ptr+1,mid+1,r,st,en));
	}
}SGT;
 
SGT sg;
 
void dfs(ll u,ll par){
	st[u] = timer;
	id[timer] = u;
	timer++;
	fx(adj[u])
		if(x.ff!=par){
			dp[x.ff] = dp[u] + c[x.ss];
			dfs(x.ff,u);
			to[x.ss] = x.ff;
		}
	en[u] = timer - 1;
	return;
}
 
void dfs2(ll u,ll par,ll k){
	aeh[u] = k;
	fx(adj[u])
		if(x.ff!=par)
			dfs2(x.ff,u,k);
	return;
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE
 
        cin>>n>>m>>tp;
        fip(0,n-1){
        	cin>>sr>>de>>tptp;
        	adj[sr].push_back({de,i});
        	adj[de].push_back({sr,i});
        	c[i] = tptp;
    	}
    	res = 0;
    	dp[1] = 0;
		dfs(1,-1);    	
		sg.init(n)	;
		sg.build(1,0,n-1);
		// fip(1,n+1)
		// 	cout<<dp[i]<<" ";
		// cout<<nli;
		// fip(1,n+1)
		// 	cout<<st[i]<<" ";
		// cout<<nli;
		// fip(1,n+1)
		// 	cout<<en[i]<<" ";
		// cout<<nli;
		// fip(0,n)
		// 	cout<<id[i]<<" ";
		// cout<<nli;
		// fip(1,n+1)
		// 	cout<<sg.query(1,0,n-1,st[i],st[i])<<" ";
		// cout<<nli;
		set<ll> s;
		fx(adj[1])
			dfs2(x.ff,1,x.ff);
		// fip(1,1+n)
		// 	cout<<aeh[i]<<" ";
		// cout<<nli;
		fx(adj[1])
			s.insert(-sg.query(1,0,n-1,st[x.ff],en[x.ff]));
		// debug(s);
    	while(m--){
    		cin>>sr>>de;
    		sr += res;
    		sr %= (n-1);
    		de += res;
    		de %= (tp);    		
    		tp2 = aeh[to[sr]];
    		ans = 0;
    		// debug(tp2);
    		s.erase(s.find(-sg.query(1,0,n-1,st[tp2],en[tp2])));
    		// debug(s);
    		sg.update(1,0,n-1,st[to[sr]],en[to[sr]],de - c[sr]);
    		c[sr] = de;
    		s.insert(-sg.query(1,0,n-1,st[tp2],en[tp2]));    		
    		// debug(s);
    		if(s.size()){
    			// debug(st);
    			tp2 = *s.begin();
    			s.erase(s.begin());
    			ans = max(ans,-tp2);
    			if(s.size())
    				ans = max(ans,-tp2-(*s.begin()));
    			s.insert(tp2);
    		}
    		cout<<ans<<nli;    		
    		res = ans;
    	}
        
    // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24920 KB Output is correct
2 Runtime error 24 ms 50300 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 46484 KB Output is correct
2 Correct 186 ms 50540 KB Output is correct
3 Correct 169 ms 50564 KB Output is correct
4 Correct 163 ms 50516 KB Output is correct
5 Correct 163 ms 50380 KB Output is correct
6 Correct 158 ms 50120 KB Output is correct
7 Correct 195 ms 53520 KB Output is correct
8 Correct 192 ms 53840 KB Output is correct
9 Correct 181 ms 53568 KB Output is correct
10 Correct 198 ms 53532 KB Output is correct
11 Correct 191 ms 53324 KB Output is correct
12 Correct 177 ms 52296 KB Output is correct
13 Correct 168 ms 58148 KB Output is correct
14 Correct 206 ms 58200 KB Output is correct
15 Correct 223 ms 58612 KB Output is correct
16 Correct 184 ms 58312 KB Output is correct
17 Correct 190 ms 57452 KB Output is correct
18 Correct 179 ms 54100 KB Output is correct
19 Correct 161 ms 58156 KB Output is correct
20 Correct 178 ms 58148 KB Output is correct
21 Correct 207 ms 58240 KB Output is correct
22 Correct 189 ms 58176 KB Output is correct
23 Correct 184 ms 57528 KB Output is correct
24 Correct 176 ms 53952 KB Output is correct

Subtask #6
0 / 27.0

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