Submission #1275922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275922		tu2108	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	233 ms	59636 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define getbit(x , i) ((x >> i) & 1)
typedef pair<int , int> pii;

const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 1e5;

int n , q , W , t = 0 , ans = 0;
int d[maxn + 5] , in[maxn + 5] , node_pos[maxn * 2 + 5] , out[maxn + 5];
vector<pii> adj[maxn + 5];

struct edge{
	int u , v , w;
};
edge e[maxn + 5];

struct node{
	int dmin;
	pii dmax;
	int premax , sufmax;
	int lazy;

	void add(const int &val){
		dmin += val; dmax.fi += val;
		lazy += val;
		premax -= val ; sufmax -= val;
	}

	void gan(){
		dmin = inf , dmax = {-inf , 0};
		premax = -inf , sufmax = -inf;
		lazy = 0;
	}

	void mrg(const node&A , const node &B){
        dmin = min(A.dmin , B.dmin);
        dmax = max(A.dmax , B.dmax);

        premax = max({A.premax , B.premax , B.dmax.fi - 2 * A.dmin});
        sufmax = max({A.sufmax , B.sufmax , A.dmax.fi - 2 * B.dmin});
	}
};
node st[8 * maxn + 5];

void dfs(int u){
	in[u] = ++t;
	node_pos[t] = u;

	for(auto v : adj[u]){
		if(in[v.fi]) continue;

		d[v.fi] = d[u] + v.se;
		dfs(v.fi);

		node_pos[++t] = u;
	}
	out[u] = t;
}

void build(int id , int l , int r){
	if(l == r){
		st[id].dmax = {d[node_pos[l]] , node_pos[l]};
		st[id].dmin = d[node_pos[l]];
		st[id].premax = st[id].sufmax = -d[node_pos[l]];
		return;
	}

	int mid = (l + r) >> 1;
	build(id * 2 , l , mid);
	build(id * 2 + 1 , mid + 1 , r);

	st[id].mrg(st[id * 2] , st[id * 2 + 1]);
}

void fix(int id){
	st[id * 2].add(st[id].lazy);
	st[id * 2 + 1].add(st[id].lazy);
	st[id].lazy = 0;
}

void update(int id , int l , int r , int u , int v , int val){
	if(v < l || r < u) return;
	if(u <= l && r <= v){
		st[id].add(val);
		return;
	}
	if(st[id].lazy) fix(id);

	int mid = (l + r) >> 1;
	update(id * 2 , l , mid , u , v , val);
	update(id * 2 + 1 , mid + 1 , r , u , v , val);

	st[id].mrg(st[id * 2] , st[id * 2 + 1]);
}

node get(int id , int l , int r , int u , int v){
	node cur;
	cur.gan();
	if(v < l || r < u) return cur;

	if(u <= l && r <= v) return st[id];
	if(st[id].lazy) fix(id);

	int mid = (l + r) >> 1;
	node getl = get(id * 2 , l , mid , u , v);
	node getr = get(id * 2 + 1 , mid + 1 , r , u , v);

	cur.mrg(getl , getr);
	return cur;
}

main()
{
    faster
    cin >> n >> q >> W;
    for(int i = 1 ; i <= n - 1 ; ++i){
    	cin >> e[i].u >> e[i].v >> e[i].w;
    	adj[e[i].u].pb({e[i].v , e[i].w});
    	adj[e[i].v].pb({e[i].u , e[i].w});
	}

	dfs(1);
	build(1 , 1 , t);

	while(q--){
		int id , val;
		cin >> id >> val;

		id = (id + ans) % (n - 1) + 1;
		val = (val + ans) % W;

		if(in[e[id].u] > in[e[id].v]) swap(e[id].u , e[id].v);

		update(1 , 1 , t , in[e[id].v] , out[e[id].v] , val - e[id].w);

		node gan = get(1 , 1 , t , 1 , t);
		int leafmax = gan.dmax.se;
		int disleaf = gan.dmax.fi;

		int res = max(get(1 , 1 , t , 1 , in[leafmax]).sufmax , get(1 , 1 , t , in[leafmax] + 1 , t).premax);

		ans = res + disleaf;
		cout << ans << '\n';

		e[id].w = val;
	}
}

Compilation message (stderr)

diameter.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 | main()
      | ^~~~

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