Submission #1168622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168622		_rain_	Dynamic Diameter (CEOI19_diameter)	C++20	18 / 100	2607 ms	172368 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)1e5;
const int MAXLOG=17;
vector<pair<int,LL>>ke[N+2];
	void add_canh(int u,int v,LL c){
		ke[u].push_back({v,c});
		ke[v].push_back({u,c});
	}

int n,q;
int u[N+2],v[N+2];
LL w,c[N+2];

class IT{
	public:
		vector<LL>st;
		vector<LL>lazy;
		#define lef(id) id*2
		#define rig(id) id*2+1
		void init(int _n){
			st.assign(_n*4+2,0);
			lazy.assign(_n*4+2,0);
			return;
		}
		void pushdown(int id){
			LL &t=lazy[id];
			lazy[lef(id)]+=t,lazy[rig(id)]+=t;
			st[lef(id)]+=t,st[rig(id)]+=t;
			t=0;
			return;
		}
		void upd(int id,int l,int r,int u,int v,LL val){
			if (l>v||r<u) return;
			if (u<=l&&r<=v) {
				st[id]+=val;
				lazy[id]+=val;
				return;
			}
			pushdown(id);
			int m=(l+r)/2;
			upd(lef(id),l,m,u,v,val);
			upd(rig(id),m+1,r,u,v,val);
			st[id]=max(st[lef(id)],st[rig(id)]);
		}
		LL Get(int id,int l,int r,int u,int v){
			if (l>v||r<u) return 0;
			if (u<=l&&r<=v) return st[id];
			pushdown(id);
			int m=(l+r)/2;
			return max(Get(lef(id),l,m,u,v),Get(rig(id),m+1,r,u,v));
		}
};
IT tree[MAXLOG+2];

	bool del[N+2]={};
	int sta[MAXLOG+2][N+2],fin[MAXLOG+2][N+2],t[MAXLOG+2];
	int up[MAXLOG+2][N+2];
	int sub[N+2];
	vector<pair<int,int>>par[N+2];
	multiset<LL> dura[N+2];
	multiset<LL>dia;

	void dfs(int u,int p){
		sub[u]=1;
		for(auto&v:ke[u]){
			if (v.first==p||del[v.first]) continue;
			dfs(v.first,u);
			sub[u]+=sub[v.first];
		}
	}
	
	int Find_centroid(int u,int p,int half){
		for(auto&v:ke[u]){
			if (v.first==p || del[v.first]) continue;
			if (sub[v.first]>half) return Find_centroid(v.first,u,half);
		}
		return u;
	}
	
	void dfs2(int dep,int root,int u,int p,LL cost=0){
		sta[dep][u]=++t[dep];
		tree[dep].upd(1,1,n,sta[dep][u],sta[dep][u],cost);
		par[u].push_back({dep,root});
		for(auto&v:ke[u]){
			if (v.first==p||del[v.first]) continue;
			if (p==u) up[dep][v.first]=v.first; else up[dep][v.first]=up[dep][u];
			dfs2(dep,root,v.first,u,cost+v.second);
		}
		fin[dep][u]=t[dep];
	}
	
	LL c_dia(int u){
		if (dura[u].empty()) return 0;
		LL cost=0;
		int turn=2;
		auto it=dura[u].end();--it;
		while (turn--){
			if (it==dura[u].end()) return cost;
			cost+=*it;
			--it;
		}
		return cost;
	}

	void build_centroid(int dep,int u){
		dfs(u,u);
		u=Find_centroid(u,u,sub[u]/2);
		
		dfs2(dep,u,u,u);
		//... NEW ACCOUNT
			for(auto&v:ke[u]){
				if (del[v.first]==1) continue;
				dura[u].insert(tree[dep].Get(1,1,n,sta[dep][v.first],fin[dep][v.first]));
			}
			dia.insert(c_dia(u));
		
		del[u]=true;
		for(auto&v:ke[u]) if (del[v.first]==0) build_centroid(dep+1,v.first);
	}
	LL Csum(int dep,int id){
		return tree[dep].Get(1,1,n,sta[dep][id],fin[dep][id]);
	}
	
	void modify(int dep,int root,int u,int v,LL add){
		if (sta[dep][u]==0||sta[dep][v]==0) return;
		int x=sta[dep][u],y=sta[dep][v];
		if (x<y) swap(u,v);
		
		dia.erase(dia.find(c_dia(root)));
		dura[root].erase(dura[root].find(Csum(dep,up[dep][u])));

	
		tree[dep].upd(1,1,n,sta[dep][u],fin[dep][u],add);

		dura[root].insert(Csum(dep,up[dep][u]));
		dia.insert(c_dia(root));
		
		return;
	}

	void run_up(int u,int v,LL add){
		for(auto&root:par[u]){
			modify(root.first,root.second,u,v,add);
		}
		return;
	}
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);

	cin>>n>>q>>w;
	for(int i=0;i<=MAXLOG;++i) tree[i].init(n);
	for(int i=0;i<n-1;++i){
		cin>>u[i]>>v[i]>>c[i];
		add_canh(u[i],v[i],c[i]);
	}
	build_centroid(0,1);

	LL last=0;
	while(q--){
		int id; LL newval;
		cin>>id>>newval;
		id=(id+last)%(n-1);
		newval=(newval+last)%w;

		run_up(u[id],v[id],newval-c[id]);
		c[id]=newval;
		cout<<(last=*dia.rbegin())<<'\n';
		
	}
}

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