Submission #1220938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220938		MateiKing80	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	413 ms	37176 KiB

diameter

#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

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

struct segTree {
	vector<int> aint;
	vector<int> lazy;
	
	void init(int n) {
		aint.resize(4 * n + 5, 0);
		lazy.resize(4 * n + 5, 0);
	}
	
	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, int 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]);
	}
	
	int 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<pii>> vec;
	map<int, int> deNorm;
	set<pii> dists;
	vector<int> ancestor, depth, tin, tout, toLeaf;
	segTree ds;
	
	Tree(int x) {
		root = x;
	}
	
	void addEdge(int u, int v, int 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);
		ancestor.resize(n, root);
		ds.init(n);
		
		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];
	}
	
	int dfs(int nod, int papa, int anc, int distUp) {
		tin[nod] = ++timer;
		depth[nod] = 1 + depth[papa];
		ds.update(1, 1, n, tin[nod], tin[nod], distUp);
		ancestor[nod] = anc;
		int 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();
		ds.init(n);
		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;
	}
	
	void update(int u, int v, int 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]});
	}
	
	int query() {
		if (n == 1)
			return 0;
		if (vec[root].size() == 1)
			return (*dists.begin()).fr;
		int ans = 0;
		auto it = dists.end();
		it --;
		ans += (*it).fr;
		it --;
		ans += (*it).fr;
		return ans;
	}
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, q, useless;
	cin >> n >> q >> useless;
	Tree ds(1);
	vector<Edge> edges;
	for (int i = 1; i < n; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		ds.addEdge(u, v, w);
		edges.push_back({u, v, w});
	}
	ds.init();
	int last = 0;
	while (q --) {
		int d, e;
		cin >> d >> e;
		d = (d + last) % (n - 1) + 1;
		e = (e + last) % useless;
		ds.update(edges[d].u, edges[d].v, e - edges[d].w);
		edges[d].w = e;
		last = ds.query();
		cout << last << '\n';
	}
}

//fac subtask-ul de toate trec prin 1

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