Submission #1235108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235108		nhnguyen14	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	3239 ms	295344 KiB

diameter

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

const int N=(int)1e5;
const int MAXLOG=17;

#define ill pair<LL,int>
#define lef(id) id*2
#define rig(id) id*2+1

	vector<int>ke[N+2];
	int x[N+2],y[N+2];
	LL c[N+2];
	int n,q;
	LL w;
	void add_canh(int u,int v,int id){
		ke[u].push_back(id) , ke[v].push_back(id);
		return;
	}
	int sz[N+2]={},dep[N+2]={};
	int sta[MAXLOG+2][N+2]={},fin[MAXLOG+2][N+2]={},time_dfs[MAXLOG+2]={};
	int root[MAXLOG+2][N+2]={};
	pair<LL,int> val[MAXLOG+2][N+2]={};
	bool del[N+2]={};
	
struct Node{
	LL mx1,mx2;
	int color_1,color_2;
	Node(){
		mx1=mx2=color_1=color_2=0;
		return;
	}
	void tang(LL x){
		if (color_1!=0) mx1+=x;
		if (color_2!=0) mx2+=x;
		return;
	}
	LL F(){
		LL sum=0;
		sum=mx1+mx2;
		return sum;
	}
};
Node st[MAXLOG+2][N*4+2];
LL lazy[MAXLOG+2][N*4+2];
LL wanh[MAXLOG+2][N*4+2];

		void upd(int dep,int id,int l,int r,int pos,LL val){
			if (l>pos||r<pos) return ;
			if (l==r) wanh[dep][id]=val;
			else {
				int m=(l+r)/2;
				upd(dep,lef(id),l,m,pos,val);
				upd(dep,rig(id),m+1,r,pos,val);
				wanh[dep][id]=max(wanh[dep][lef(id)],wanh[dep][rig(id)]);
			}
		}


bool maximize(LL &a,LL b){
	if (a<b) return a=b,true;
	return false;
}

Node operator + (Node a,Node b){
	LL mx=0;
	Node res=Node();
	maximize(mx,a.mx1) , maximize(mx,a.mx2) , maximize(mx,b.mx1) , maximize(mx,b.mx2);
	if (mx==a.mx1) res.mx1=a.mx1,res.color_1=a.color_1; 
	if (mx==a.mx2) res.mx1=a.mx2,res.color_1=a.color_2;
	if (mx==b.mx1) res.mx1=b.mx1,res.color_1=b.color_1;
	if (mx==b.mx2) res.mx1=b.mx2,res.color_1=b.color_2;
	mx=0;
	if (a.color_1!=res.color_1) maximize(mx,a.mx1);
	if (a.color_2!=res.color_1) maximize(mx,a.mx2);
	if (b.color_1!=res.color_1) maximize(mx,b.mx1);
	if (b.color_2!=res.color_1) maximize(mx,b.mx2);
	
	if (a.color_1!=res.color_1 && a.mx1==mx) res.mx2=a.mx1,res.color_2=a.color_1; 
	if (a.color_2!=res.color_1 && a.mx2==mx) res.mx2=a.mx2,res.color_2=a.color_2;
	if (b.color_1!=res.color_1 && b.mx1==mx) res.mx2=b.mx1,res.color_2=b.color_1;
	if (b.color_2!=res.color_1 && b.mx2==mx) res.mx2=b.mx2,res.color_2=b.color_2;
	return res;
}

void build_tang(int tang,int id=1,int l=1,int r=n){
	if (l==r) {
		st[tang][id]=Node();
		st[tang][id].mx1=val[tang][l].first;
		st[tang][id].color_1=val[tang][l].second;
		return;
	}
	else {
		int m=(l+r)/2;
		build_tang(tang,lef(id),l,m);
		build_tang(tang,rig(id),m+1,r);
		st[tang][id]=st[tang][lef(id)]+st[tang][rig(id)];
	}
}

void pushdown(int tang,int id){
	LL &x=lazy[tang][id];
	lazy[tang][lef(id)]+=x , lazy[tang][rig(id)]+=x;
	st[tang][lef(id)].tang(x) , st[tang][rig(id)].tang(x);
	x=0;
	return;
}

void upd(int tang,int id,int l,int r,int u,int v,LL add){
	if (l>v||r<u) return;
	if (u<=l&&r<=v) {
		st[tang][id].tang(add);
		lazy[tang][id]+=add;
		return;
	}
	int m=(l+r)/2;
	pushdown(tang,id);
	upd(tang,lef(id),l,m,u,v,add);
	upd(tang,rig(id),m+1,r,u,v,add);
	st[tang][id]=st[tang][lef(id)]+st[tang][rig(id)];
	return;	
}
Node Get(int tang,int id,int l,int r,int u,int v){
	if (l>v||r<u) return Node();
	if (u<=l&&r<=v) return st[tang][id];
	int m=(l+r)/2;
	pushdown(tang,id);
	return Get(tang,lef(id),l,m,u,v)+Get(tang,rig(id),m+1,r,u,v);
}

namespace Wanh{
	void pre_dfs(int u,int p){
		sz[u]=1;
		for(auto&id:ke[u]){
			int v=u^x[id]^y[id];
			if (del[v]||v==p) continue;
			pre_dfs(v,u);
			sz[u]+=sz[v];
		}
		return;
	}
	
	int Find_centroid(int u,int p,int half){
		for(auto&id:ke[u]){
			int v=u^x[id]^y[id];
			if (v==p||del[v]) continue;
			if (sz[v]>half) return Find_centroid(v,u,half);
  		}
		return u;
	}
	
	void dfs_build(int dep,int u,int p,int Faker,int cur_color,LL cost=0){
		sta[dep][u]=++time_dfs[dep];
		root[dep][u]=Faker;
		val[dep][sta[dep][u]]={cost,cur_color};
		int cur=cur_color;
		for(auto&id:ke[u]){
			int v=u^x[id]^y[id];
			if (v==p||del[v]) continue;
			if (cur_color==0) ++cur;
			dfs_build(dep,v,u,Faker,cur,cost+c[id]);
		}
		fin[dep][u]=time_dfs[dep];
	}
	
	void build(int u,int p){
		pre_dfs(u,u);
		u=Find_centroid(u,u,sz[u]/2);	
			del[u]=true;
			dep[u]=dep[p]+1;		
		dfs_build(dep[u],u,u,u,0);		
		for(auto&id:ke[u]){
			int v=u^x[id]^y[id];
			if (del[v]) continue;
			build(v,u);
		}
		return;
	}
}
using namespace Wanh;
	
	void modify(int dep,int u,int v,LL cost){
		if (sta[dep][u]<sta[dep][v]) swap(u,v);
		int l=sta[dep][u],r=fin[dep][u];
		upd(dep,1,1,time_dfs[dep],l,r,cost);
	}
	
	void change_canh(int u,int v,LL cost){
		for(int i=min(dep[u],dep[v]);i>=1;--i) {
			int r=root[i][u];
			modify(i,u,v,cost);
			LL k=Get(i,1,1,time_dfs[i],sta[i][r],fin[i][r]).F();
			upd(i,1,1,time_dfs[i],sta[i][r],k);
		}
		return;
	}

LL duongkinh(){
	LL ans=0;
	for(int i=1;i<=MAXLOG && time_dfs[i]>0;++i) ans=max(ans,wanh[i][1]);
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	
	#define name "main"
	if (fopen(name".inp","r")){
		freopen(name".inp","r",stdin);
		freopen(name".out","w",stdout);
	}
	
	cin>>n>>q>>w;
	for(int i=0;i<n-1;++i) {
		cin>>x[i]>>y[i]>>c[i];
		add_canh(x[i],y[i],i);
	}
	build(1,0);
	for(int i=1;i<=MAXLOG && time_dfs[i];++i) build_tang(i,1,1,time_dfs[i]);
	for(int i=1;i<=n;++i) {
		LL k=Get(dep[i],1,1,time_dfs[dep[i]],sta[dep[i]][i],fin[dep[i]][i]).F();
		upd(dep[i],1,1,time_dfs[dep[i]],sta[dep[i]][i],k);
	}
	LL last=0;
	while(q--){
		int d;
		LL e; cin>>d>>e;
		d=(last+d)%(n-1) , e=(last+e)%w;
		int change_cost=e-c[d];
		c[d]+=change_cost;
		change_canh(x[d],y[d],change_cost);
		LL ans=duongkinh();
		cout<<ans<<'\n';
		last=ans;
	}
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:211:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |                 freopen(name".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:212:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |                 freopen(name".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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