Submission #199388

#	Time	Username	Problem	Language	Result	Execution time	Memory
199388		gs18081	Dynamic Diameter (CEOI19_diameter)	C++11	100 / 100	751 ms	54348 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 101010;

struct segtree{
	struct Node{
		ll a,b,ab,ba,aba;
		Node(){
			a = b = ab = ba = aba = 0;
		}
		Node operator+(Node c){
			Node ret;
			ret.aba = max({c.aba , aba , ab + c.a , a + c.ba});
			ret.ab = max({ab , c.ab , a + c.b});
			ret.ba = max({ba , c.ba , b + c.a});
			ret.b = max({b , c.b});
			ret.a = max({a , c.a});
			return ret;
		}
	};
	int n;
	vector<Node> tree;
	vector<ll> lazy;
	segtree(){}
	void resize(int size){
		n = size;
		tree = vector<Node> (n * 4);
		lazy = vector<ll> (n*4,0);
	}
	void laz(int node,int s,int e){
		if(s != e){
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];
		}
		tree[node].a += lazy[node];
		tree[node].b -= 2 * lazy[node];
		tree[node].ab -= lazy[node];
		tree[node].ba -= lazy[node];
		lazy[node] = 0;
	}
	Node update(int node,int s,int e,int l,int r,ll diff){
		laz(node,s,e);
		if(e < l||r < s) return tree[node];
		if(l <= s && e <= r){
			lazy[node] += diff;
			laz(node,s,e);
			return tree[node];
		}
		int m = (s + e) >> 1;
		return tree[node] = update(node<<1,s,m,l,r,diff) + update(node<<1|1,m+1,e,l,r,diff);
	}
	void update(int l,int r,ll diff){
		update(1,1,n,l,r,diff);
		//printf("%d %d %lld %lld\n",l,r,diff,tree[1].aba);
	}
	ll getroot(){
		return tree[1].aba;
	}
}myseg;

int N,Q;
ll W;
int s[MAXN];
int e[MAXN];
int t;
int pedge[MAXN];
vector<pi> edge[MAXN];
ll elen[MAXN];
ll ans = 0;

void dfs(int node){
	s[node] = e[node] = ++t;
	for(auto i : edge[node]){
		if(s[i.first]) continue;
		pedge[i.second] = i.first;
		dfs(i.first);
		e[node] = ++t;
	}
}




int main(){
	scanf("%d %d %lld",&N,&Q,&W);
	for(int i=0;i<N-1;i++){
		int a,b;
		scanf("%d %d %lld",&a,&b,&elen[i]);
		edge[a].push_back(pi(b,i));
		edge[b].push_back(pi(a,i));
	}
	dfs(1);
	myseg.resize(t);
	for(int i=0;i<N-1;i++){
		myseg.update(s[pedge[i]],e[pedge[i]],elen[i]);
	}
	for(int i=0;i<Q;i++){
		int D;
		ll E;
		scanf("%d %lld",&D,&E);
		D = (D + ans) % (N - 1);
		E = (E + ans) % W;
		myseg.update(s[pedge[D]],e[pedge[D]],E - elen[D]);
		elen[D] = E;
		ans = myseg.getroot();
		printf("%lld\n",ans);
	}

	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:90: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:93: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:105: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: 24 / 24
• Subtask 6: 27 / 27