Submission #834622

#	Time	Username	Problem	Language	Result	Execution time	Memory
834622		Elias	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5101 ms	394940 KiB

diameter

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") // codeforces
#endif

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

template <class T>
istream &operator>>(istream &in, vector<T> &a)
{
	for (T &x : a)
		in >> x;
	return in;
}

template <class T>
ostream &operator<<(ostream &out, const vector<T> &a)
{
	for (T x : a)
		out << x << " ";
	out << "\n";
	return out;
}

struct SegTree
{
	pair<int, int> get(int l, int r)
	{
		return get(0, n, 0, l, r);
	}
	void inc(int l, int r, int x)
	{
		inc(0, n, 0, l, r, x);
	}

	SegTree(const vector<int> &a)
	{
		n = a.size();
		updates = vector<int>(4 * n);
		b = vector<pair<int, int>>(4 * n);
		build(0, n, 0, a);
	}

	SegTree() {}

private:
	int n = 0;
	vector<pair<int, int>> b = {};
	vector<int> updates = {};

	void push(int l, int r, int i)
	{
		if (l + 1 == r)
			return;
		updates[i * 2 + 1] += updates[i];
		updates[i * 2 + 2] += updates[i];
		b[i * 2 + 1].first += updates[i];
		b[i * 2 + 2].first += updates[i];
		updates[i] = 0;
	}

	pair<int, int> build(int l, int r, int i, const vector<int> &a)
	{
		if (l + 1 == r)
			return b[i] = pair<int, int>{a[l], l};
		int m = (l + r) / 2;
		return b[i] = max(build(l, m, i * 2 + 1, a), build(m, r, i * 2 + 2, a));
	}

	pair<int, int> get(int l, int r, int i, int ql, int qr)
	{
		if (l >= qr || r <= ql)
			return {LLONG_MIN / 2, -1};
		if (l >= ql && r <= qr)
			return b[i];
		push(l, r, i);
		int m = (l + r) / 2;
		return max(get(l, m, i * 2 + 1, ql, qr), get(m, r, i * 2 + 2, ql, qr));
	}

	pair<int, int> inc(int l, int r, int i, int ul, int ur, int x)
	{
		if (l >= ur || r <= ul)
			return b[i];
		if (l >= ul && r <= ur)
		{
			updates[i] += x;
			b[i].first += x;
			return b[i];
		}
		push(l, r, i);
		int m = (l + r) / 2;
		return b[i] = max(inc(l, m, i * 2 + 1, ul, ur, x), inc(m, r, i * 2 + 2, ul, ur, x));
	}
};

vector<vector<pair<int, int>>> adj;
vector<bool> blocked;

struct Tree
{
	int n = 0;

	unordered_map<int, int> pre;
	unordered_map<int, int> subtree;
	unordered_map<int, int> initial_parent;

	vector<int> pre_order;
	vector<int> pre_dist;

	int timer = 0;
	int centroid = -1;

	SegTree pre_dist_seg;

	void spread(int i, int p = -1)
	{
		n++;
		for (auto [c, D] : adj[i])
		{
			if (c != p && !blocked[c])
			{
				spread(c, i);
			}
		}
	}

	int find_centroid(int i, int p = -1)
	{
		int subtree_size = 1;
		int largest_subtree = 0;

		for (auto [c, D] : adj[i])
		{
			if (c != p && !blocked[c])
			{
				int sub = find_centroid(c, i);
				subtree_size += sub;
				largest_subtree = max(largest_subtree, sub);
			}
		}

		if (largest_subtree <= n / 2 && n - subtree_size <= n / 2)
			centroid = i;

		return subtree_size;
	}

	int dfs(int i, int d = 0, int p = -1)
	{
		pre[i] = timer++;
		pre_order.push_back(i);
		pre_dist[pre[i]] = d;

		int subtree_size = 1;

		if (p == -1)
			initial_parent[i] = -1;
		else if (initial_parent[p] == -1)
			initial_parent[i] = i;
		else
			initial_parent[i] = initial_parent[p];

		for (auto [c, D] : adj[i])
		{
			if (c != p && !blocked[c])
			{
				subtree_size += dfs(c, d + D, i);
			}
		}

		subtree[i] = subtree_size;

		return subtree_size;
	}

	vector<int> split()
	{
		blocked[centroid] = true;
		vector<int> out;
		for (auto [c, d] : adj[centroid])
		{
			if (!blocked[c])
				out.push_back(c);
		}
		return out;
	}

	Tree(int start)
	{
		spread(start);
		pre_dist = vector<int>(n);

		find_centroid(start);

		assert(centroid != -1);

		dfs(centroid);

		pre_dist_seg = SegTree(pre_dist);
	}

	int update(int a, int b, int c)
	{
		if (subtree.count(a) != 0 && subtree.count(b) != 0)
		{
			if (pre[a] > pre[b])
				swap(a, b);

			int dist_lower = pre_dist_seg.get(pre[b], pre[b] + 1).first;
			int dist_upper = pre_dist_seg.get(pre[a], pre[a] + 1).first;

			int old_weight = dist_lower - dist_upper;

			int delta = c - old_weight;
			pre_dist_seg.inc(pre[b], pre[b] + subtree[b], delta);
		}

		auto [dist, i] = pre_dist_seg.get(0, n);
		int bad_child = initial_parent[pre_order[i]];

		auto dist2 = pre_dist_seg.get(0, pre[bad_child]).first;
		auto dist3 = pre_dist_seg.get(pre[bad_child] + subtree[bad_child], n).first;

		return dist + max({dist2, dist3, 0l});
	}
};

signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n, q, w;
	cin >> n >> q >> w;

	adj.resize(n);
	blocked.resize(n);

	vector<pair<int, int>> all_edges;

	for (int i = 0; i < n - 1; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;

		adj[a].push_back({b, c});
		adj[b].push_back({a, c});

		all_edges.push_back({a, b});
	}

	vector<Tree> subtrees;
	subtrees.push_back(Tree(0));

	queue<int> todo;
	todo.push(0);

	vector<vector<int>> trees_using(n, {0});

	while (todo.size())
	{
		int index = todo.front();
		todo.pop();

		auto out = subtrees[index].split();
		for (auto x : out)
		{
			Tree new_tree(x);
			if (new_tree.n > 1)
			{
				int new_index = subtrees.size();
				todo.push(new_index);

				for (auto i : new_tree.pre_order)
				{
					if (trees_using[i].back() != new_index)
						trees_using[i].push_back(new_index);
				}

				subtrees.push_back(move(Tree(x)));
			}
		}
	}

	vector<int> subtree_result(subtrees.size());

	set<pair<int, int>> results;

	for (int i = 0; i < subtrees.size(); i++)
	{
		subtree_result[i] = subtrees[i].update(-1, -1, -1);
		results.insert({subtree_result[i], i});
	}

	int last = 0;

	while (q--)
	{
		int d, e;
		cin >> d >> e;
		d = (d + last) % int(n - 1);
		e = (e + last) % w;

		auto [a, b] = all_edges[d];

		int out = 0;

		for (int i : trees_using[a])
		{
			results.erase({subtree_result[i], i});
			subtree_result[i] = subtrees[i].update(a, b, e);
			results.insert({subtree_result[i], i});
		}

		out = prev(results.end())->first;

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

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:296:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |  for (int i = 0; i < subtrees.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

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