Submission #594046

#	Time	Username	Problem	Language	Result	Execution time	Memory
594046		penguinhacker	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	1675 ms	164104 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

struct seg_tree {
	int n;
	vector<ll> st, lz;
	seg_tree() {}
	seg_tree(int n) : n(n) {
		st.resize(4*n);
		lz.resize(4*n);
	}
	void init(vector<ll>& a) {
		assert(a.size()==n);
		bld(1, 0, n-1, a);
	}
	void bld(int u, int l, int r, vector<ll>& a) {
		if (l==r) {
			st[u]=a[l];
			return;
		}
		int mid=(l+r)/2;
		bld(2*u, l, mid, a);
		bld(2*u+1, mid+1, r, a);
		st[u]=max(st[2*u], st[2*u+1]);
	}
	void psh(int u, int l, int r) {
		if (lz[u]) {
			st[u]+=lz[u];
			if (l!=r)
				lz[2*u]+=lz[u], lz[2*u+1]+=lz[u];
			lz[u]=0;
		}
	}
	void upd(int ql, int qr, ll x, int u, int l, int r) {
		psh(u, l, r);
		if (l>qr||r<ql)
			return;
		if (ql<=l&&r<=qr) {
			lz[u]+=x;
			psh(u, l, r);
			return;
		}
		int mid=(l+r)/2;
		upd(ql, qr, x, 2*u, l, mid);
		upd(ql, qr, x, 2*u+1, mid+1, r);
		st[u]=max(st[2*u], st[2*u+1]);
	}
	void upd(int ql, int qr, ll x) {
		upd(ql, qr, x, 1, 0, n-1);
	}
	ll qry(int ql, int qr, int u, int l, int r) {
		psh(u, l, r);
		if (l>qr||r<ql)
			return 0;
		if (ql<=l&&r<=qr)
			return st[u];
		int mid=(l+r)/2;
		return max(qry(ql, qr, 2*u, l, mid), qry(ql, qr, 2*u+1, mid+1, r));
	}
	ll qry(int ql, int qr) {
		return qry(ql, qr, 1, 0, n-1);
	}
};

struct PQ {
	vector<ll> d;
	priority_queue<pair<ll, int>> pq;
	PQ() {}
	PQ(vector<ll> d) : d(d) {
		for (int i=0; i<d.size(); ++i)
			push(i);
	}
	void push(int i) {
		pq.emplace(d[i], i);
	}
	void upd(int i, ll x) {
		pq.emplace(d[i]=x, i);
	}
	void norm() {
		while(pq.size()&&pq.top().first!=d[pq.top().second])
			pq.pop();
	}
	ll top() {
		norm();
		return pq.size()?pq.top().first:0;
	}
	ll diam() {
		norm();
		ll a=top(), b=0;
		if (pq.size()) {
			int last=pq.top().second;
			pq.pop();
			norm();
			b=top();
			push(last);
		}
		return a+b;
	}
};

const int mxN=1e5;
int n, q, eu[mxN], ev[mxN], s[mxN], tin[mxN], t;
ll wlim, ew[mxN];
vector<int> adj[mxN], child_tin[mxN], child_tout[mxN];
bool dead[mxN];
vector<ll> init_dist, init_diam;
vector<ar<int, 4>> by_edge[mxN]; // which trees is this edge on, {tree, tree_child, tin, tout}
seg_tree st[mxN];
PQ best_children[mxN], ans;

int dfs1(int u, int p) { // get size
	s[u]=1;
	for (int e : adj[u]) {
		int v=eu[e]^ev[e]^u;
		if (v!=p&&!dead[v])
			s[u]+=dfs1(v, u);
	}
	return s[u];
}

int get_centroid(int u) {
	int ts=dfs1(u, -1);
	bool ok=1;
	while(ok) {
		ok=0;
		for (int e : adj[u]) {
			int v=eu[e]^ev[e]^u;
			if (s[v]<s[u]&&!dead[v]&&s[v]>ts/2) {
				ok=1;
				u=v;
				break;
			}
		}
	}
	return u;
}

int rt, rt_child;

void dfs2(int u, int p, ll d) {
	tin[u]=t++;
	init_dist.push_back(d);
	for (int e : adj[u]) {
		int v=eu[e]^ev[e]^u;
		if (v!=p&&!dead[v]) {
			dfs2(v, u, d+ew[e]);
			by_edge[e].push_back({rt, rt_child, tin[v], t-1});
			if (p==-1) {
				child_tin[rt].push_back(tin[v]);
				child_tout[rt].push_back(t-1);
				++rt_child;
			}
		}
	}
}

void solve(int u=0) {
	//cout << u << endl;
	u=get_centroid(u);
	dead[u]=1;
	//cout << u << endl;

	t=0, rt=u, rt_child=0;
	init_dist.clear();
	dfs2(u, -1, 0);
	//cout << u << endl;
	st[u]=seg_tree(t);
	st[u].init(init_dist);
	//cout << u << " " << t << endl;
	vector<ll> init_best;
	for (int i=0; i<rt_child; ++i)
		init_best.push_back(st[u].qry(child_tin[u][i], child_tout[u][i]));
	//cout << u << endl;
	best_children[u]=PQ(init_best);
	init_diam[u]=best_children[u].diam();

	for (int e : adj[u])
		if (!dead[eu[e]^ev[e]^u])
			solve(eu[e]^ev[e]^u);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> wlim;
	for (int i=0; i<n-1; ++i) {
		cin >> eu[i] >> ev[i] >> ew[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	init_diam.resize(n);
	solve();
	ans=PQ(init_diam);
	ll last=0;
	while(q--) {
		int i;
		ll nxt;
		cin >> i >> nxt;
		i=(i+last)%(n-1);
		nxt=(nxt+last)%wlim;
		//cout << i << " " << nxt << endl;
		ll change=nxt-ew[i];
		for (auto [u, x, a, b] : by_edge[i]) {
			//cout << u << " " << x << " " << a << " " << b << endl;
			st[u].upd(a, b, change);
			best_children[u].upd(x, st[u].qry(child_tin[u][x], child_tout[u][x]));
			ans.upd(u, best_children[u].diam());
		}
		ew[i]=nxt;
		cout << (last=ans.top()) << "\n";
	}
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from diameter.cpp:1:
diameter.cpp: In member function 'void seg_tree::init(std::vector<long long int>&)':
diameter.cpp:16:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |   assert(a.size()==n);
      |          ~~~~~~~~^~~
diameter.cpp: In constructor 'PQ::PQ(std::vector<long long int>)':
diameter.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i=0; i<d.size(); ++i)
      |                 ~^~~~~~~~~

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