Submission #968347

#	Time	Username	Problem	Language	Result	Execution time	Memory
968347		shadow_sami	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3903 ms	386504 KiB

diameter

#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;
const ll mxn = 20;
vector<pi> adj[mx];
ll aa[mx];
ll bb[mx];
ll c[mx];
ll val[mx];
ll to[mx][mxn];
bool mark[mx];
ll sz[mx];
ll st[mx][mxn];
ll en[mx][mxn];
ll id[mx][mxn];
ll id2[mx][mxn];
ll sr,de;
ll timer[mxn];
 
typedef struct SEGMENT_TREE{
	vi arr;
	vi laz;
	vi mid;
	ll range;
	void init(ll k){
		range = 4 * k;
		arr.resize(range);
		mid.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] = 0;
			return arr[ptr];
		}
		mid[ptr] = l + (r-l) / 2;
		build(2*ptr,l,mid[ptr]);
		build(2*ptr+1,mid[ptr]+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];
		}
		update(2*ptr,l,mid[ptr],st,en,val);
		update(2*ptr+1,mid[ptr]+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];		
		return max(query(2*ptr,l,mid[ptr],st,en),query(2*ptr+1,mid[ptr]+1,r,st,en));
	}
}SGT;
 
SGT sg[mxn];
priority_queue<pi> les[mx];
priority_queue<pi> sol,ptt;
ll dp[mx][mxn];
ll dp2[mx];

void dfs(ll u,ll par){
	sz[u] = 1;
	fx(adj[u]){
		if(x.ff==par || mark[x.ff])continue;
		dfs(x.ff,u);
		sz[u] += sz[x.ff];
	}
	return;
}

ll get(ll u,ll par,ll k){
	fx(adj[u]){
		if(x.ff==par || mark[x.ff])continue;
		if(sz[x.ff]*2>k)
			return get(x.ff,u,k);
	}
	return u;
}

void ds(ll u,ll par,ll k,ll d,ll p,ll pp){	
	to[u][k] = par;
	id[u][k] = p;
	id2[u][k] = pp;
	st[u][k] = timer[k]++;
	sg[k].update(1,0,n-1,st[u][k],st[u][k],d);
	fx(adj[u]){
		if(x.ff==par || mark[x.ff])continue;
		ds(x.ff,u,k,d+c[x.ss],p,pp);		
	}
	en[u][k] = timer[k]-1;
	return;
}
pi pt,pt2;

ll calc(ll d,ll k){
	while(les[d].size()&& dp[les[d].top().ss][k]!=les[d].top().ff)
		les[d].pop();
	if(!les[d].size())
		return 0;
	// ptt = les[d];
	// while(ptt.size()){
	// 	debug(ptt.top());
	// 	ptt.pop();
	// }
	// cerr<<nli;
	pt = les[d].top();
	// debug(pt);
	pt2 = {0,0};
	while(les[d].size() && ((dp[les[d].top().ss][k]!=les[d].top().ff) || (les[d].top()==pt))){
		// debug(les[d].top());
		// debug(pt);
		// debug((dp[les[d].top().ss][k]));
		// cerr<<nli;
		les[d].pop();	
	}
	// debug((ll)les[d].size());
	// ptt = les[d];
	// while(ptt.size()){
	// 	debug(ptt.top());
	// 	ptt.pop();
	// }
	// cerr<<nli;
	if(les[d].size())
		pt2 = les[d].top();
	// debug(pt2);
	les[d].push(pt);
	return pt.ff+pt2.ff;
}

void divide(ll u,ll d){
	dfs(u,-1);	
	u = get(u,-1,sz[u]);	
	// debug(u);	
	mark[u] = 1;
	val[u] = d;
	fx(adj[u])
		if(!mark[x.ff]){
			ds(x.ff,u,d,c[x.ss],u,x.ff);
			les[u].push({dp[x.ff][d] = sg[d].query(1,0,n-1,st[x.ff][d],en[x.ff][d]),x.ff});
		}
	// fip(1,n+1)
	// 	cerr<<st[i][d]<<" ";
	// cerr<<nli;
	// fip(1,n+1)
	// 	cerr<<en[i][d]<<" ";
	// cerr<<nli;
	// ptt = les[u];
	// while(ptt.size()){
	// 	debug(ptt.top());
	// 	ptt.pop();
	// }
	// cerr<<nli;
	sol.push({dp2[u] = calc(u,d),u});
	// ptt = sol;
	// while(ptt.size()){
	// 	// debug(ptt.top());
	// 	ptt.pop();
	// }
	// cerr<<nli;
	// // cerr<<"non"<<nli;
	// // 	ptt = les[1];
	// // 	while(ptt.size()){
	// // 		debug(ptt.top());
	// // 		ptt.pop();
	// // 	}
	// // 	cerr<<nli;
	fx(adj[u])
		if(!mark[x.ff])
			divide(x.ff,d+1);	
	return;
}

void update(ll a,ll b){
	// debug(a);
	// debug(b);
	fjp(0,mxn){
		if(val[a]<j || val[b]<j)
			break;
		if(to[a][j]==b)
			swap(a,b);
		// debug(id[b][j]);
		// debug(de-c[sr]);
		// debug(id2[b][j]);
		// debug(st[b][j]);
		// debug(en[b][j]);
		// fip(1,n+1)
		// 	cerr<<sg[j].query(1,0,n-1,st[i][j],st[i][j])<<" ";
		// cerr<<nli;
		sg[j].update(1,0,n-1,st[b][j],en[b][j],de-c[sr]);
		// ptt = les[id[b][j]];
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
		les[id[b][j]].push({dp[id2[b][j]][j] = sg[j].query(1,0,n-1,st[id2[b][j]][j],en[id2[b][j]][j]),id2[b][j]});		
		// ptt = les[id[b][j]];
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
		// cerr<<"calc"<<nli;
		sol.push({dp2[id[b][j]] = calc(id[b][j],j),id[b][j]});
		// cerr<<"calc"<<nli;
		// ptt = les[id[b][j]];
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
	}
	while(sol.size() && dp2[sol.top().ss]!=sol.top().ff)
		sol.pop();

	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;
        	aa[i] = sr;
        	bb[i] = de;
    	}
    	res = 0;
    	fip(0,mxn){
    		sg[i].init(n);
			sg[i].build(1,0,n-1);
    	}
		divide(1,0);
		// ptt = sol;
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
		// cerr<<"non"<<nli;
		// ptt = les[1];
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
		// cerr<<nli;
		// cerr<<"start"<<nli;
    	while(m--){
    		cin>>sr>>de;
    		sr += res;
    		sr %= (n-1);
    		de += res;
    		de %= (tp);    		
    		ans = 0;
    		// debug(sr);
    		// debug(de);

    		update(aa[sr],bb[sr]);
    		ans = sol.top().ff;
    		c[sr] = de;
    		cout<<ans<<nli;    		
    		res = ans;
    	}
        
    // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27