Submission #634689

#	Time	Username	Problem	Language	Result	Execution time	Memory
634689		BackNoob	Dynamic Diameter (CEOI19_diameter)	C++14	0 / 100	5065 ms	490548 KiB

diameter

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}


struct IT{
	int n;
	vector<ll> t;
	vector<ll> lz;
	IT(){}
	IT(int _n) {
		n = _n;
		t.resize(n * 4 + 7, 0);
		lz.resize(n * 4 + 7, 0);
	}

	void push_down(int v)
	{
		for(int i = v * 2; i <= v * 2 + 1; i++) {
			t[i] += lz[v];
			lz[i] += lz[v];
		}
		lz[v] = 0;
	}

	void update(int v, int tl, int tr, int l, int r, ll val)
	{
		if(l > r) return;
		if(tl == l && tr == r) {
			t[v] += val;
			lz[v] += val;
		}
		else {
			push_down(v);
			int tm = (tl + tr) / 2;
			update(v * 2, tl, tm, l, min(r, tm), val);
			update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}

	ll getmax(int v, int tl, int tr, int l, int r)
	{
		if(l > r) return 0;
		if(tl == l && tr == r) return t[v];
		push_down(v);
		int tm = (tl + tr) / 2;
		ll m1 = getmax(v * 2, tl, tm, l, min(r, tm));
		ll m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
		return max(m1, m2);
	}

	void update(int l, int r, ll val)
	{
		update(1, 1, n, l, r, val);
	}
	ll getmax(int l, int r)
	{
		return getmax(1, 1, n, l, r);
	}
} seg[mxN];


struct ITmax{
	int n;
	vector<ll> t;
	ITmax(){}
	ITmax(int _n) {
		n = _n;
		t.resize(n * 4 + 7, 0);
	}

	void update(int v, int tl, int tr, int pos, ll val)
	{
		if(tl == tr) t[v] = val;
		else {
			int tm = (tl + tr) / 2;
			if(pos <= tm) update(v * 2, tl, tm, pos, val);
			else update(v * 2 + 1, tm + 1, tr, pos, val);
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}

	ll getmax(int v, int tl, int tr, int l, int r)
	{
		if(l > r) return 0;
		if(tl == l && tr == r) return t[v];
		int tm = (tl + tr) / 2;
		ll m1 = getmax(v * 2, tl, tm, l, min(r, tm));
		ll m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
		return max(m1, m2);
	}

	void update(int pos, ll val)
	{
		update(1, 1, n, pos, val);
	}
	ll getmax(int l, int r)
	{
		return getmax(1, 1, n, l, r);
	}
} maxval;


struct EDGE{
	int u, v;
	ll c;
} ed[mxN];


int n;
int q;
ll lim;
int sub[mxN];
int par[mxN];
bool removed[mxN];
vector<int> cen[mxN];
vector<pair<int, ll>> adj[mxN];
map<int, int> sta[mxN];
map<int, int> fin[mxN];
map<int, int> part[mxN];
map<int, ll> dist[mxN];
multiset<pair<ll, int>> ms[mxN];
int timer = 0;

void dfs_sz(int u, int p)
{
	sub[u] = 1;
	for(auto it : adj[u]) {
		int v = it.fi;
		if(v == p || removed[v] == true) continue;
		dfs_sz(v, u);
		sub[u] += sub[v];
	}
}

int find_centroid(int u, int p, int n)
{
	for(auto it : adj[u]) {
		int v = it.fi;
		if(v == p || removed[v] == true) continue;
		if(sub[v] > n / 2) return find_centroid(v, u, n);
	}
	return u;
}

void dfs(int u, int p, int root, ll cur, int group)
{
	part[root][u] = group;
	dist[root][u] = cur;
	sta[root][u] = ++timer;
	seg[root].update(timer, timer, cur);
	for(auto it : adj[u]) {
		int v = it.fi;
		ll c = it.se;
		if(v == p || removed[v] == true) continue;

		if(u == root) dfs(v, u, root, cur + c, v);
		else dfs(v, u, root, cur + c, group);
	}
	fin[root][u] = timer;
}

void update_maxval(int p)
{
	ll val = 0;
	if(sz(ms[p]) == 1) {
		pair<ll, int> tmp = *ms[p].begin();
		val = tmp.fi;
	} 	
	if(sz(ms[p]) > 1) {
		auto it = ms[p].end();
		--it;
		pair<ll, int> tmp;
		tmp = *it;
		val += tmp.fi;
		--it;
		tmp = *it;
		val += tmp.fi;
	}

	// cout << p << ' ' << val << endl;
	maxval.update(p, val);
}

void init_centroid(int u, int p)
{
	timer = 0;
	dfs_sz(u, -1);
	int c = find_centroid(u, -1, sub[u]);
	par[c] = p;

	seg[c] = IT(sub[u]);
	dfs(c, -1, c, 0, 0);	

	for(auto it : adj[c]) {
		int v = it.fi;
		if(removed[it.fi] == false) cen[c].pb(v);
	}


	for(auto it : cen[c]) {
		int l = sta[c][it];
		int r = fin[c][it];


		ll val = seg[c].getmax(l, r);
		ms[c].insert(make_pair(val, it));
	}

	update_maxval(c);

	removed[c] = true;
	for(auto it : adj[c]) {
		int v = it.fi;
		if(removed[v] == true) continue;;
	 	init_centroid(v, c);
	}
}

void update(int u, int v, ll w)
{
	set<int> node;
	int x = u;
	int y = v;
	while(x != -1) {
		node.insert(x);
		x = par[x];
		if(sta[x].count(u) == 0 || sta[x].count(v) == 0 || fin[x].count(u) == 0 || fin[x].count(v) == 0) continue;
		int lu = sta[x][u];
		int ru = fin[x][u];
		int lv = sta[x][v];
		int rv = fin[x][v];

		if(lu <= lv && rv <= ru) {
			int cc = part[x][v];
			ll val = seg[x].getmax(sta[x][cc], fin[x][cc]);
			ms[x].erase(ms[x].find(make_pair(val, cc)));
			seg[x].update(lv, rv, w);
			val = seg[x].getmax(sta[x][cc], fin[x][cc]);
			ms[x].insert(make_pair(val, cc));

		}
		if(lv <= lu && ru <= rv) {
			int cc = part[x][u];
			ll val = seg[x].getmax(sta[x][cc], fin[x][cc]);
			ms[x].erase(ms[x].find(make_pair(val, cc)));
			seg[x].update(lu, ru, w);
			val = seg[x].getmax(sta[x][cc], fin[x][cc]);
			ms[x].insert(make_pair(val, cc));

		}
		update_maxval(x);
	}

	while(y != -1) {
		if(node.find(y) != node.end()) break;
		// cerr << y << endl;
		y = par[y];
		if(sta[y].count(u) == 0 || sta[y].count(v) == 0 || fin[y].count(u) == 0 || fin[y].count(v) == 0) continue;
		int lu = sta[y][u];
		int ru = fin[y][u];
		int lv = sta[y][v];
		int rv = fin[y][v];

		if(lu <= lv && rv <= ru) {
			int cc = part[y][v];
			ll val = seg[y].getmax(sta[y][cc], fin[y][cc]);
			ms[y].erase(ms[y].find(make_pair(val, cc)));
			seg[y].update(lv, rv, w);
			val = seg[y].getmax(sta[y][cc], fin[y][cc]);
			ms[y].insert(make_pair(val, cc));

		}
		if(lv <= lu && ru <= rv) {
			int cc = part[y][u];
			ll val = seg[y].getmax(sta[y][cc], fin[y][cc]);
			ms[y].erase(ms[y].find(make_pair(val, cc)));
			seg[y].update(lu, ru, w);
			val = seg[y].getmax(sta[y][cc], fin[y][cc]);
			ms[y].insert(make_pair(val, cc));
		}
		update_maxval(y);
	}
}

void solve()
{
	cin >> n >> q >> lim;
	for(int i = 1; i < n; i++) {
		int u, v;
		ll c;
		cin >> u >> v >> c;
		adj[u].pb({v, c});
		adj[v].pb({u, c});
		ed[i] = {u, v, c};
	}

	maxval = ITmax(n);
	init_centroid(1, -1);	

	// cout << maxval.getmax(1, n) << endl;
	// return;

	ll last = 0;
	while(q--) {
		ll idx;
		ll w;
		cin >> idx >> w;

		idx = (idx + last) % (n - 1);
		w = (w + last) % lim;	

		// cout << idx << ' ' << w << endl;
		update(ed[idx + 1].u, ed[idx + 1].v, w - ed[idx + 1].c);
		ed[idx + 1].c = w;
		// update(ed[idx + 1].u, ed[idx + 1].v, ed[idx + 1].c);

		last = maxval.getmax(1, n);
		cout << last << endl;
	}

	// for(int i = 1; i < n; i++) cout << ed[i].u << ' ' << ed[i].v << ' ' << ed[i].c << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

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