Submission #1220935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220935		MateiKing80	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	5107 ms	440368 KiB

diameter

#pragma GCC optimize("O4")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
//#define int ll

using pii = pair<int, int>;
#define fr first
#define sc second

const int N = 1e5 + 5;

struct Edge {
	int u, v;
	ll w;
};

struct segTree {
	vector<ll> aint;
	vector<ll> lazy;
	vector<ll> v;
	
	void build(int pos, int st, int dr) {
		if (st == dr) {
			aint[pos] = v[st];
			return;
		}
		int mid = (st + dr) >> 1;
		build(2 * pos, st, mid);
		build(2 * pos + 1, mid + 1, dr);
		aint[pos] = max(aint[2 * pos], aint[2 * pos + 1]);
	}
	
	void init(int n, vector<ll> x) {
		aint.resize(4 * n + 5, 0);
		lazy.resize(4 * n + 5, 0);
		v = x;
		build(1, 1, n);
	}
	
	void propag(int pos) {
		if (lazy[pos] == 0)
			return;
		aint[pos] += lazy[pos];
		if (2 * pos + 1 < (int)lazy.size()) {
			lazy[2 * pos] += lazy[pos];
			lazy[2 * pos + 1] += lazy[pos];
		}
		lazy[pos] = 0;
	}
	
	void update(int pos, int st, int dr, int l, int r, ll val) {
		propag(pos);
		if (l <= st && dr <= r) {
			lazy[pos] += val;
			propag(pos);
			return;
		}
		int mid = (st + dr) >> 1;
		
		if (l <= mid)
			update(2 * pos, st, mid, l, r, val);
		else
			propag(2 * pos);
	
		if (mid < r)
			update(2 * pos + 1, mid + 1, dr, l, r, val);
		else
			propag(2 * pos + 1);
			
		aint[pos] = max(aint[2 * pos], aint[2 * pos + 1]);
	}
	
	ll query(int pos, int st, int dr, int l, int r) {
		propag(pos);
		if (l <= st && dr <= r)
			return aint[pos];
		int mid = (st + dr) >> 1;
		if (r <= mid)
			return query(2 * pos, st, mid, l, r);
		if (mid < l)
			return query(2 * pos + 1, mid + 1, dr, l, r);
		return max(query(2 * pos, st, mid, l, r), query(2 * pos + 1, mid + 1, dr, l, r));
	}
};

struct Tree {
	int root, n, timer = 0;
	vector<Edge> edges;
	vector<vector<pair<int, ll>>> vec;
	map<int, int> deNorm;
	set<pair<ll, int>> dists;
	vector<int> ancestor, depth, tin, tout;
	vector<ll> toLeaf, forBuild;
	segTree ds;
	
	void addEdge(int u, int v, ll w) {
		edges.push_back({u, v, w});
	}
	
	void addVec() {
		n = edges.size() + 1;
		vec.resize(n);
		depth.resize(n, 0);
		tin.resize(n, 0);
		tout.resize(n, 0);
		toLeaf.resize(n, 0);
		forBuild.resize(n + 1, 0);
		ancestor.resize(n, root);
		
		map<int, int> mp;
		for (auto [u, v, w] : edges)
			mp[u] ++, mp[v] ++;
		int cnt = 0;
		for (auto [i, j] : mp)
			deNorm[i] = cnt ++;
		for (auto [u, v, w] : edges) {
			vec[deNorm[u]].push_back({deNorm[v], w});
			vec[deNorm[v]].push_back({deNorm[u], w});
		}
		root = deNorm[root];
	}
	
	ll dfs(int nod, int papa, int anc, ll distUp) {
		tin[nod] = ++timer;
		depth[nod] = 1 + depth[papa];
		forBuild[tin[nod]] = distUp;
		ancestor[nod] = anc;
		ll maxx = 0;
		for (auto [i, j] : vec[nod]) {
			if (i == papa)
				continue;
			maxx = max(maxx, j + dfs(i, nod, anc, distUp + j));
		}
		tout[nod] = timer;
		return maxx;
	}
	
	void init() {
		addVec();
		tin[root] = ++timer;
		for (auto [i, j] : vec[root]) {
			toLeaf[i] = j + dfs(i, root, i, j);
			dists.insert({toLeaf[i], i});
		}
		tout[root] = timer;
		ds.init(n, forBuild);
	}
	
	void update(int u, int v, ll diff) {
		u = deNorm[u];
		v = deNorm[v];		

		if (depth[u] < depth[v])
			swap(u, v);
		ds.update(1, 1, n, tin[u], tout[u], diff);
		dists.erase({toLeaf[ancestor[u]], ancestor[u]});
		toLeaf[ancestor[u]] = ds.query(1, 1, n, tin[ancestor[u]], tout[ancestor[u]]);
		dists.insert({toLeaf[ancestor[u]], ancestor[u]});
	}
	
	ll query() {
		if (n == 1)
			return 0;
		if (vec[root].size() == 1)
			return (*dists.begin()).fr;
		ll ans = 0;
		auto it = dists.end();
		it --;
		ans += (*it).fr;
		it --;
		ans += (*it).fr;
		return ans;
	}
} ds[N];

set<pair<ll, int>> s;
vector<pair<int, ll>> vec[N];
int papaC[N];
int depthCentr[N];

bool isCentroid[N];
int sz[N];

void dfsSz(int nod, int papa) {
	sz[nod] = 1;
	for (auto [i, j] : vec[nod])
		if (i != papa && !isCentroid[i]) {
			dfsSz(i, nod);
			sz[nod] += sz[i];
		}
}

int centr(int nod, int papa, int target) {
	for (auto [i, j] : vec[nod])
		if (!isCentroid[i] && i != papa && sz[i] >= target)
			return centr(i, nod, target);
	return nod;
}

void dfsAddDs(int nod, int papa, int c) {
	for (auto [i, j] : vec[nod]) {
		if (i != papa && !isCentroid[i]) {
			ds[c].addEdge(i, nod, j);
			dfsAddDs(i, nod, c);
		}
	}
}

void dfsCentroid(int nod, int papaCentr) {
	dfsSz(nod, 0);
	int c = centr(nod, 0, (sz[nod] + 1) / 2);
	papaC[c] = papaCentr;
	depthCentr[c] = 1 + depthCentr[papaCentr];
	isCentroid[c] = true;
	dfsAddDs(c, 0, c);
	for (auto [i, j] : vec[c])
		if (!isCentroid[i])
			dfsCentroid(i, c);
}

ll precAns[N];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, q;
	ll useless;
	cin >> n >> q >> useless;
	for (int i = 1; i <= n; i ++)
		ds[i].root = i;
	vector<Edge> edges;
	for (int i = 1; i < n; i ++) {
		int u, v;
		ll w;
		cin >> u >> v >> w;
		edges.push_back({u, v, w});
		vec[u].push_back({v, w});
		vec[v].push_back({u, w});
	}
	dfsCentroid(1, 0);
	for (int i = 1; i <= n; i ++) {	
		ds[i].init();
		precAns[i] = ds[i].query();
		s.insert({precAns[i], i});
	}
	ll last = 0;
	while (q --) {
		int d;
		ll e;
		cin >> d >> e;
		d = (d + last) % (n - 1) + 1;
		d --;
		e = (e + last) % useless;
		int u = edges[d].u;
		int v = edges[d].v;
		ll w = e - edges[d].w;
		if (depthCentr[u] > depthCentr[v])
			swap(u, v);	
				
		int curr = u;
		while (curr) {
			s.erase({precAns[curr], curr});
			ds[curr].update(u, v, w);
			precAns[curr] = ds[curr].query();
			s.insert({precAns[curr], curr});
			curr = papaC[curr];
		}
		last = (*s.rbegin()).fr;
		edges[d].w = e;
		cout << last << '\n';
	}
}

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