Submission #834447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
834447	2023-08-22T14:27:44 Z	Elias	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	5000 ms	377780 KB

diameter

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) (x).begin(), (x).end()

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
{
	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();
		b = updates = vector<int>(4 * n);
		build(0, n, 0, a);
	}

	SegTree() {}

private:
	int n = 0;
	vector<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] += updates[i];
		b[i * 2 + 2] += updates[i];
		updates[i] = 0;
	}

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

	int get(int l, int r, int i, int ql, int qr)
	{
		if (l >= qr || r <= ql)
			return LLONG_MIN / 2;
		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));
	}

	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] += 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));
	}
};

struct Tree
{
	int n;

	map<int, vector<pair<int, int>>> edges;

	map<int, int> pre;
	map<int, int> subtree;

	vector<int> pre_dist;

	int timer = 0;
	int centroid = -1;

	SegTree pre_dist_seg;

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

		for (auto [c, D] : edges[i])
		{
			if (c != p)
			{
				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;
	}

	void get_edges(int i, int p, map<int, vector<pair<int, int>>> &out)
	{
		for (auto [c, d] : edges[i])
		{
			if (c == centroid)
				continue;
			out[i].push_back({c, d});
			if (c != p)
				get_edges(c, i, out);
		}
	}

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

		int subtree_size = 1;

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

		subtree[i] = subtree_size;

		return subtree_size;
	}

	vector<map<int, vector<pair<int, int>>>> split()
	{
		vector<map<int, vector<pair<int, int>>>> out;
		for (auto [c, d] : edges[centroid])
		{
			map<int, vector<pair<int, int>>> subset;
			get_edges(c, centroid, subset);
			out.push_back(move(subset));
		}
		return out;
	}

	Tree(map<int, vector<pair<int, int>>> edges) : edges{edges}
	{
		n = edges.size();
		pre_dist = vector<int>(n);

		int start;

		for (auto [i, c] : edges)
		{
			start = i;
			break;
		}

		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)
			return 0;

		if (pre[a] > pre[b])
			swap(a, b);

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

		int old_weight = dist_lower - dist_upper;

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

		int largest = 0;
		int second = 0;

		for (auto [c, d] : edges[centroid])
		{
			int dist = pre_dist_seg.get(pre[c], pre[c] + subtree[c]);
			if (dist >= largest)
			{
				second = largest;
				largest = dist;
			}
			else if (dist >= second)
			{
				second = dist;
			}
		}

		return largest + second;
	}
};

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

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

	map<int, vector<pair<int, int>>> edges;

	vector<pair<int, int>> all_edges;

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

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

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

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

	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)
		{
			if (x.size() > 1)
			{
				int new_index = subtrees.size();
				todo.push(new_index);
				subtrees.push_back(Tree(x));
				for (auto [i, c] : x)
				{
					if (trees_using[i].back() != new_index)
						trees_using[i].push_back(new_index);
				}
			}
		}
	}

	int last = 0;

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

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

		int out = 0;

		for (int i : trees_using[a])
		{
			out = max(out, subtrees[i].update(a, b, e));
		}

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

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Correct	28 ms	468 KB	Output is correct
5	Correct	115 ms	1356 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct
8	Correct	16 ms	624 KB	Output is correct
9	Correct	129 ms	652 KB	Output is correct
10	Correct	1032 ms	868 KB	Output is correct
11	Execution timed out	5027 ms	2052 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-