Submission #226578

#	Time	Username	Problem	Language	Result	Execution time	Memory
226578		oolimry	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	3282 ms	184688 KiB

diameter

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
const long long inf = (1LL << 60LL);

typedef pair<long long, long long> ii;
struct edge { long long u, v, w; vector<int> trees; vector<ii> preorder; };

struct segment{
	int n;
	vector<ii> tree;
	vector<long long> lazy;
	vector<ii> assocBlock;
	long long ans = 0;
	
	void relax(int i){
		if(i < n) tree[i] = max(tree[i<<1], tree[i<<1|1]);		
		else tree[i] = ii(0,i-n);
		tree[i].first += lazy[i];
	}
	
	void create(int _n){
		n = _n;
		tree.assign(2*n, ii(0,0));
		assocBlock.assign(n, ii(0,0));
		lazy.assign(2*n,0);
		for(int i = 2*n-1;i>0;i--) relax(i);
	}
	
	void update(int L, int R, long long v){
		for(int l = L + n, r = R + n;l < r;l >>= 1, r >>= 1){
			if(l&1){
				lazy[l] += v;
				relax(l);
				l++;
			}
			if(r&1){
				r--;
				lazy[r] += v;
				relax(r);
			}
		}
		for(int l = L + n;l > 0;l >>= 1) relax(l);
		for(int r = R + n - 1;r > 0;r >>= 1) relax(r);
	}
	
	long long query(){
		ans = tree[1].first;
		ii block = assocBlock[tree[1].second];
		update(block.first, block.second+1, -inf);
		ans += tree[1].first;
		update(block.first, block.second+1, inf);
		return ans;
	}
};

vector<segment> trees;
segment overall;

long long n, Q, WMAX;
vector<edge> edges;
vector<ii> adj[100005];
vector<int> Cnodes;
bool cented[100005];
int sz[100005];

int dfs(int u, int p){
	Cnodes.push_back(u);
	sz[u] = 1;
	for(ii v : adj[u]){
		if(v.first == p) continue;
		if(cented[v.first]) continue;
		sz[u] += dfs(v.first, u);
	}
	return sz[u];
}

vector<ii> ranges;
int cnt = 0;
ii dfs2(int u, int p){
	ii res = ii(cnt,cnt); cnt++;
	for(ii v : adj[u]){
		if(v.first == p) continue;
		if(cented[v.first]) continue;
		
		ii vRes = dfs2(v.first, u);
		res.second = max(res.second, vRes.second);
		
		edges[v.second].trees.push_back((int) trees.size());
		edges[v.second].preorder.push_back(vRes);
		
		if(p == -1) ranges.push_back(vRes);
	}
	return res;
}

void recurse(int A){
	dfs(A, -1);
	
	int R;
	for(int u : Cnodes){
		int maxSz = sz[A] - sz[u];
		for(ii v : adj[u]){
			if(cented[v.first]) continue;
			if(sz[v.first] < sz[u]) maxSz = max(maxSz, sz[v.first]);
		}
		if(2*maxSz <= (int) sz[A]){
			R = u;
			break;
		}
	}
	
	cnt = 0; dfs2(R, -1);
	trees.push_back({});
	trees.back().create(cnt);
	for(ii r : ranges){
		for(int i = r.first;i <= r.second;i++) trees.back().assocBlock[i] = ii(r);
	}
	
	cented[R] = true;
	Cnodes.clear(); ranges.clear();
	for(ii v : adj[R]){
		if(!cented[v.first]) recurse(v.first);
	}
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> Q >> WMAX;
	for(int i = 0;i < n-1;i++){
		int u, v, w; cin >> u >> v >> w; u--; v--;
		edges.push_back({u,v,w,{},{}});
		adj[u].push_back(ii(v,i));
		adj[v].push_back(ii(u,i));
	}
	recurse(0);
	
	for(edge e : edges){
		for(int i = 0;i < (int) e.preorder.size();i++){
			ii x = e.preorder[i];
			trees[e.trees[i]].update(x.first, x.second+1, e.w);
		}
	}
	
	overall.create(n);
	for(int i = 0;i < n;i++) overall.update(i,i+1,trees[i].query());
	
	long long ans = 0;
	while(Q--){
		long long E, w; cin >> E >> w;
		E = (E + ans) % (n-1); w = (w + ans) % WMAX;
		edge e = edges[E];
		
		long long diff = w - e.w;
		
		for(int i = 0;i < (int) e.preorder.size();i++){
			ii x = e.preorder[i];
			int treeNo = e.trees[i];
			long long preAns = trees[treeNo].ans;
			trees[treeNo].update(x.first, x.second+1, diff);
			long long diff2 = trees[treeNo].query() - preAns;
			overall.update(treeNo,treeNo+1,diff2);
		}
		
		edges[E].w = w;
		ans = overall.tree[1].first;
		cout << ans << "\n";
	}
}

Compilation message (stderr)

diameter.cpp: In function 'void recurse(long long int)':
diameter.cpp:103:6: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int R;
      ^

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