Submission #884735

#	Time	Username	Problem	Language	Result	Execution time	Memory
884735		arashMLG	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	338 ms	157012 KiB

diameter

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;


const int N = 1e6+ 23;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)
#define int         ll

struct node {
	int diam;
	int leftMax;
	int rightMax;
	int mxh,mnh;
	int lz;
	
	void set(int h) {
		diam = 0;
		leftMax = -h;
		rightMax = -h;
		mxh = h,mnh = h;
		lz = 0;
	}
	
	
	void merge(node a,node b) {
		mxh = max(a.mxh,b.mxh);
		mnh = min(a.mnh,b.mnh);
		
		leftMax = max({a.leftMax, b.leftMax ,b.mxh - 2*a.mnh});
		rightMax =max({a.rightMax,b.rightMax,a.mxh - 2*b.mnh});
		
		diam = max({ a.diam, b.diam, a.rightMax + b.mxh , b.leftMax+ a.mxh});
	}
} t[N<<2];

int n,q;
int h[N];
int st[N],ft[N];
int what[N];

void build(int v=1,int tl =0,int tr= N) {
	if(tr-tl == 1) {
		t[v].set(h[what[tl]]);
		return;
	}
	int mid=(tl+tr)/2;
	build(lc,tl,mid);
	build(rc,mid,tr);
	t[v].merge(t[lc],t[rc]);
	//debug(tl,tr,t[v].diam,t[v].leftMax,t[v].rightMax);
}

void shift(int v) {
	int x = t[v].lz;
	t[lc].leftMax -= x;
	t[lc].rightMax -= x;
	t[lc].mxh += x;
	t[lc].mnh += x;
	t[lc].lz += x;
	t[rc].leftMax -= x;
	t[rc].rightMax -= x;
	t[rc].mxh += x;
	t[rc].mnh += x;
	t[rc].lz += x;
	t[v].lz = 0;
}

void upd(int l,int r,int x,int v=1,int tl=0,int tr =N) {
	if(l > r) return;
	if(l == tl && r == tr-1) {
		t[v].leftMax -= x;
		t[v].rightMax -= x;
		t[v].mxh += x;
		t[v].mnh += x;
		t[v].lz += x;
		return;
	}
	shift(v);
	int mid=(tl + tr)/2;
	upd(l,min(mid-1,r),x,lc,tl,mid);
	upd(max(l,mid),r,x,rc,mid,tr);
	t[v].merge(t[lc],t[rc]);
}

int W;
int w[N];
int ver[N];
vector<pll> G[N];
int timer;

void dfs(int v,int p =-1) {
	what[timer] = v;
	st[v] = timer ++;
	for(auto [u,id] : G[v]) if(u != p) {
		ver[id] = u;
		h[u] = h[v] + w[id];
		dfs(u,v);
		what[timer] = v;
		ft[v]= timer ++;
	}
	
	what[timer] = v;
	ft[v]= timer ++;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>q>>W;
	int last= 0;
	for(int i = 0; i<n-1 ; i ++) {
		int v,u; cin>>v>>u>>w[i];
		G[v].pb({u,i});
		G[u].pb({v,i});
	}
	dfs(1);
	build();
	debug(t[1].diam);
	while(q--) {
		int e,d; cin>>e>>d;
		e= (e + last) % (n-1);
		d= (d +last) % W;
		int v= ver[e];
		//debug(st[v],ft[v]);
		upd(st[v],ft[v],-w[e]);
		w[e] = d;
		upd(st[v],ft[v],w[e]);
		last = t[1].diam;
		cout<<last << '\n';
	}
	
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int32_t main()':
diameter.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
diameter.cpp:135:2: note: in expansion of macro 'debug'
  135 |  debug(t[1].diam);
      |  ^~~~~

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