Submission #276006

#	Time	Username	Problem	Language	Result	Execution time	Memory
276006		theStaticMind	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	931 ms	30944 KiB

diameter

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
int S;
struct MaxSeg{
	vector<int> seg;
	vector<int> lazy;

	MaxSeg(int N);
	void build();
	void push(int j);
	void pull(int j);
	void rangeupdate(int j, int x, int y, int l, int r, int v);
	int rangequery(int j, int x, int y, int l, int r);
} seg(100005);


int n;

vector<ii> adj[100005];
vector<ii> edge;
int anc[100005];
int depth[100005];
int T[100005];
int X[100005];

multiset<int> data;
map<int, int> ptr;

int getedge(int x, int y){
	return lower_bound(all(adj[x]), ii{y, -1}) - adj[x].begin();
}

void update(int y){
	data.erase(data.lower_bound(ptr[y]));
	ptr[y] = seg.rangequery(1, 0, S - 1, T[y], X[y]);
	data.insert(ptr[y]);
}

void init(int x, int pre){
	static int time = 1;
	T[x] = time++;
	
	if(pre == 1)anc[x] = x;
	
	for(auto p : adj[x]){
		int y = p.first;
		if(y == pre) continue;
		
		anc[y] = anc[x];
		depth[y] = depth[x] + 1;

		init(y, x);

	}
	X[x] = time - 1;
}


vector<int> dp(100005, 0);
void naive(int x, int pre){

	for(auto p : adj[x]){
		int y = p.first;
		if(y == pre) continue;
		
		dp[y] = dp[x] + p.second;

		naive(y, x);

	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int q, W;
	cin >> n >> q >> W;

	for(int i = 0; i < n - 1; i++){
		int x, y, z;
		cin >> x >> y >> z;
		adj[x].pb({y, z});
		adj[y].pb({x, z});

		edge.pb({x, y});
	}

	for(int i = 1; i <= n; i++){
		sort(all(adj[i]));
	}

	init(1, 0);
	naive(1, 0);

	for(int i = 1; i <= n; i++){
		seg.rangeupdate(1, 0, S - 1, T[i], T[i], dp[i]);
	}

	int last = 0;

	for(auto p : adj[1]){
		ptr[p.first] = seg.rangequery(1, 0, S - 1, T[p.first], X[p.first]);
		data.insert(ptr[p.first]);
	}

	while(q--){ 
		ii p;
		cin >> p.first >> p.second;
		p.first = (p.first + last) % (n - 1);
		p.second = (p.second + last) % W;
		int x = edge[p.first].first;
		int y = edge[p.first].second;
		int z = p.second;

		if(depth[x] > depth[y]) swap(x, y);
		
		seg.rangeupdate(1, 0, S - 1, T[y], X[y], z - adj[x][getedge(x, y)].second);
		update(anc[y]);
		
		adj[x][getedge(x, y)].second = z;
		adj[y][getedge(y, x)].second = z;

		last = *data.rbegin();
		if(sz(data) > 1)  last += *++data.rbegin();

		cout << last << "\n";
	}
}

MaxSeg::MaxSeg(int N){
	seg= vector<int>(N, 0);
	build();
}

void MaxSeg::build(){
	S = 1 << (int)ceil(log2(sz(seg)));
	while(sz(seg) != S) seg.pb(0);
	reverse(all(seg));
	for(int i = 1; i < sz(seg); i += 2) seg.pb(max(seg[i - 1], seg[i]));
	seg.pb(0);
	reverse(all(seg));
	lazy = vector<int> (sz(seg), 0);
}

void MaxSeg::push(int j){
	if(j < sz(seg)){
		seg[j] += lazy[j];
		if(j * 2 < sz(seg)){
			lazy[j*2] += lazy[j];
			lazy[j*2+1] += lazy[j];
		}
		lazy[j] = 0;
	}
}

void MaxSeg::pull(int j){
	push(j);
	push(j*2);
	push(j*2+1);
	if(j * 2 < sz(seg)){
		seg[j] = max(seg[j*2], seg[j*2+1]);
	}
}

void MaxSeg::rangeupdate(int j, int x, int y, int l, int r, int v){
	if(y < l || r < x) return;
	push(j);
	if(l <= x && y <= r){
		lazy[j] += v;
	}
	else{
		rangeupdate(j*2,x,(x+y)/2,l,r,v);
		rangeupdate(j*2+1,(x+y)/2+1,y,l,r,v);
	}
	pull(j);
}

int MaxSeg::rangequery(int j, int x, int y, int l, int r){
	if(y < l || r < x) return 0;
	push(j);
	if(l <= x && y <= r){
		return seg[j];
	}
	else{
		return max(
			rangequery(j*2,x,(x+y)/2,l,r),
			rangequery(j*2+1,(x+y)/2+1,y,l,r)
			);
	}
}

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