Submission #199356

#	Time	Username	Problem	Language	Result	Execution time	Memory
199356		gs18081	Dynamic Diameter (CEOI19_diameter)	C++11	49 / 100	5035 ms	121656 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll,ll> pl;

const int MAXN = 101010;

struct segtree{
	int n;
	ll tree[MAXN * 4];
	int pos[MAXN * 4];
	ll lazy[MAXN * 4];
	segtree(){}
	void resize(int size){
		n = size;
		init(1,1,n);
	}
	void init(int node,int s,int e){
		if(s == e){
			pos[node] = s;
			return;
		}
		int m = (s + e) >> 1;
		init(node<<1,s,m);
		init(node<<1|1,m+1,e);
		upnode(node);
	}
	void upnode(int node){
		if(tree[node<<1] >= tree[node<<1|1]){
			tree[node] = tree[node<<1];
			pos[node] = pos[node<<1];
		}
		else{
			tree[node] = tree[node<<1|1];
			pos[node] = pos[node<<1|1];
		}
	}
	void laz(int node,int s,int e){
		if(s != e){
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];
		}
		tree[node] += lazy[node];
		lazy[node] = 0;
	}
	void update(int node,int s,int e,int l,int r,ll diff){
		laz(node,s,e);
		if(e < l||r < s) return;
		if(l <= s && e <= r){
			lazy[node] += diff;
			laz(node,s,e);
			return ;
		}
		int m = (s + e) >> 1;
		update(node<<1,s,m,l,r,diff);
		update(node<<1|1,m+1,e,l,r,diff);
		upnode(node);
	}
	void update(int l,int r,ll diff){
		update(1,1,n,l,r,diff);
	}
	pl range(int node,int s,int e,int l,int r){
		laz(node,s,e);
		if(e < l||r < s) return pl(0,0);
		if(l <= s && e <= r) return pl(tree[node],pos[node]);
		int m = (s + e) >> 1;
		return max(range(node<<1,s,m,l,r) , range(node<<1 | 1 ,m+1,e,l,r));
	}
	pl range(int l,int r){
		return range(1,1,n,l,r);
	}
};

int N,Q;
ll W;
ll prevans = 0;
int siz[MAXN];
int prtedge[20][MAXN];
int cprt[MAXN];
int dep[MAXN];
vector<pl> edge[MAXN];
int vis[MAXN];
int cprtnode[MAXN];
int s[20][MAXN];
int e[20][MAXN];
int rdfn[20][MAXN];
int t[20];
ll elen[MAXN];
segtree myseg[20];

int szdfs(int node,int par){
	siz[node] = 1;
	for(auto i : edge[node]) if(i.first != par && !vis[i.first]) siz[node] += szdfs(i.first,node);
	return siz[node];
}

int cdfs(int node,int par,int cap){
	for(auto i : edge[node]) if(i.first != par && !vis[i.first] && siz[i.first] > cap) return cdfs(i.first,node,cap);
	return node;
}

int dfs(int node,int par,int d){
	e[d][node] = s[d][node] = ++t[d];
	rdfn[d][s[d][node]] = node;
	for(auto i : edge[node]){
		if(i.first == par|| vis[i.first]) continue;
		prtedge[d][i.second] = i.first;
		e[d][node] = dfs(i.first,node,d);
	}
//	printf("%d %d %d %d\n",node,d,s[d][node],e[d][node]);
	return e[d][node];
}



int decomp(int node,int par){
	int cap = szdfs(node,par);
	int cen = cdfs(node,par,cap/2);
	cprt[cen] = par;
	dep[cen] = dep[par] + 1;
	dfs(cen,par,dep[cen]);
	vis[cen] = 1;
	for(auto i : edge[cen]){
		if(i.first == par || vis[i.first]) continue;
		int tcen = decomp(i.first,cen);
		cprtnode[tcen] = i.first;
	}
	assert(dep[cen] < 20);
//	printf("ang %d %d\n",cen,par);
	return cen;
}

pl getfar(int node){
	pl ret = pl(0,0);
	int now = node;
	int prv = -1;
	while(now != 0){
		pl temp = pl(0,0);
		if(prv != -1){
			int tprv = cprtnode[prv];
			temp = max(temp , myseg[dep[now]].range(s[dep[now]][now] , s[dep[now]][tprv] - 1));
			temp = max(temp , myseg[dep[now]].range(e[dep[now]][tprv] + 1 , e[dep[now]][now]));
		}
		else temp = myseg[dep[now]].range(s[dep[now]][now],e[dep[now]][now]);
		temp.second = rdfn[dep[now]][temp.second];
		temp.first += myseg[dep[now]].range(s[dep[now]][node],s[dep[now]][node]).first;
		//printf("%d %d %lld %lld\n",node,now,temp.first,temp.second);
		ret = max(temp,ret);
		prv = now;
		now = cprt[now];
	}
	return ret;
}

int main(){
	scanf("%d %d %lld",&N,&Q,&W);
	for(int i=0;i<20;i++) myseg[i].resize(N);
	for(int i=0;i<N-1;i++){
		int a,b;
		scanf("%d %d %lld",&a,&b,&elen[i]);
		edge[a].push_back(pl(b,i));
		edge[b].push_back(pl(a,i));
	}
	dep[0] = -1;
	int allcen = decomp(1,0);
	for(int i=0;i<N-1;i++){
		for(int j=0;j<20;j++){
			if(!prtedge[j][i]) continue;
			//printf("prtedge %d %d %d\n",j,i,prtedge[j][i]);
			myseg[j].update(s[j][prtedge[j][i]] , e[j][prtedge[j][i]] , elen[i]);
		}
	}
	for(int i=0;i<Q;i++){
		int d;
		ll E;
		scanf("%d %lld",&d,&E);
		d = (0LL + d + prevans) % (N - 1);
		E = (E + prevans) % W;
		//printf("query %d %lld\n",d,E);
		for(int j=0;j<20;j++){
			if(!prtedge[j][d]) continue;
		//	printf("updating %d %d %d\n",j, s[j][prtedge[j][d]] , e[j][prtedge[j][d]] );
			myseg[j].update(s[j][prtedge[j][d]] , e[j][prtedge[j][d]] , E - elen[d]);
		}
		elen[d] = E;
		pl temp = getfar(allcen);
		temp = getfar(temp.second);
		prevans = temp.first;
		printf("%lld\n",prevans);
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld",&N,&Q,&W);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&a,&b,&elen[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %lld",&d,&E);
   ~~~~~^~~~~~~~~~~~~~~~~

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