Submission #276001

#	Time	Username	Problem	Language	Result	Execution time	Memory
276001		AKaan37	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	2218 ms	15208 KiB

diameter

//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 100005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,x[li],y[li],z[li],mx,ind,dep[li],st[li],en[li],lazy[li*4],say,hedef;
int cev;
PII tree[li];
multiset<int> stt;
string s;
vector<PII> v[li];

inline void dfs(int node,int ata,int der){
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i].fi;
		int co=v[node][i].se;
		if(go==ata)continue;
		dfs(go,node,der+co);
	}
	if(der>mx)ind=node;
	mx=max(mx,der);
	dep[node]=der;
}

inline void dfs1(int node,int ata){
	flag=0;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i].fi;
		if(go==ata)continue;
		flag=1;
		dfs1(go,node);
		if(st[node]==0)st[node]=st[go];
		else st[node]=min(st[node],st[go]);
		en[node]=max(en[node],en[go]);
	}
	if(flag==0){
		st[node]=++say;
		en[node]=say;
	}
}

inline void build(int node,int start,int end){
	if(start==end){tree[node]={dep[start],start};return ;}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline void push(int node,int start,int end){
	if(lazy[node]==0)return ;
	tree[node].fi+=lazy[node];
	if(start!=end){
		lazy[node*2]+=lazy[node];
		lazy[node*2+1]+=lazy[node];
	}
	lazy[node]=0;
}

inline void update(int node,int start,int end,int l,int r,int val){
	push(node,start,end);
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		lazy[node]=val;
		push(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline void update1(int node,int start,int end,int l,int r,int val){
	push(node,start,end);
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		tree[node]={val,start};
		return ;
	}
	update1(node*2,start,mid,l,r,val),update1(node*2+1,mid+1,end,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline PII query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return {0,0};
	push(node,start,end);
	if(start>=l && end<=r)return tree[node];
	return max(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
}

int32_t main(void){
	scanf("%lld %lld %lld",&n,&t,&k);
	int yes=0;
	for(int i=1;i<n;i++){
		scanf("%lld %lld %lld",&x[i],&y[i],&z[i]);
		stt.insert(z[i]);
		if(x[i]==1)yes++;
		if(y[i]==1)yes++;
	}
	if(n*t<=5000*5000){
		while(t--){
			int d,e;
			scanf("%lld %lld",&d,&e);
			z[(d+cev)%(n-1)+1]=(cev+e)%k;
			FOR v[i].clear();
			for(int i=1;i<n;i++){
				v[x[i]].pb({y[i],z[i]});
				v[y[i]].pb({x[i],z[i]});
			}
			mx=0;
			dfs(1,0,0);
			mx=0;
			dfs(ind,0,0);
			cev=mx;
			printf("%lld\n",cev);
		}
		return 0;
	}
	if(yes==n-1){
		while(t--){
			int d,e;
			scanf("%lld %lld",&d,&e);
			stt.erase(stt.find(z[(d+cev)%(n-1)+1]));
			z[(d+cev)%(n-1)+1]=(cev+e)%k;
			stt.insert(z[(d+cev)%(n-1)+1]);
			auto it=stt.end();
			if(it==stt.begin()){cev=0;printf("%lld\n",cev);continue;}
			it--;
			cev=*it;
			if(it==stt.begin()){printf("%lld\n",cev);continue;}
			it--;
			cev+=*it;
			printf("%lld\n",cev);
		}
		return 0;
	}
	dfs(1,0,0);
	dfs1(1,0);
	while(t--){
		int d,e;
		scanf("%lld %lld",&d,&e);
		if(dep[y[(d+cev)%(n-1)+1]]<dep[x[(d+cev)%(n-1)+1]])swap(x[(d+cev)%(n-1)+1],y[(d+cev)%(n-1)+1]);
		update(1,1,say,st[y[(d+cev)%(n-1)+1]],en[y[(d+cev)%(n-1)+1]],-z[(d+cev)%(n-1)+1]);
		z[(d+cev)%(n-1)+1]=(cev+e)%k;
		update(1,1,say,st[y[(d+cev)%(n-1)+1]],en[y[(d+cev)%(n-1)+1]],z[(d+cev)%(n-1)+1]);
		PII at=query(1,1,say,1,say);
		cev=at.fi;
		int tut=cev;
		update1(1,1,say,at.se,at.se,0);
		cev+=query(1,1,say,1,say).fi;
		update1(1,1,say,at.se,at.se,tut);
		printf("%lld\n",cev);
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int32_t main()':
diameter.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |  scanf("%lld %lld %lld",&n,&t,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |   scanf("%lld %lld %lld",&x[i],&y[i],&z[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:124:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |    scanf("%lld %lld",&d,&e);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
diameter.cpp:143:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  143 |    scanf("%lld %lld",&d,&e);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
diameter.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |   scanf("%lld %lld",&d,&e);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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