Submission #834452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
834452	2023-08-22T14:29:59 Z	Elias	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	5000 ms	335836 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;

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

	unordered_map<int, int> pre;
	unordered_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, unordered_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<unordered_map<int, vector<pair<int, int>>>> split()
	{
		vector<unordered_map<int, vector<pair<int, int>>>> out;
		for (auto [c, d] : edges[centroid])
		{
			unordered_map<int, vector<pair<int, int>>> subset;
			get_edges(c, centroid, subset);
			out.push_back(move(subset));
		}
		return out;
	}

	Tree(unordered_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;

	unordered_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;
	}
}

Compilation message

diameter.cpp: In constructor 'Tree::Tree(std::unordered_map<long long int, std::vector<std::pair<long long int, long long int> > >)':
diameter.cpp:187:7: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  187 |   int start;
      |       ^~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	22 ms	408 KB	Output is correct
5	Correct	105 ms	676 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	7 ms	596 KB	Output is correct
9	Correct	64 ms	608 KB	Output is correct
10	Correct	627 ms	716 KB	Output is correct
11	Correct	3196 ms	1044 KB	Output is correct
12	Correct	15 ms	3156 KB	Output is correct
13	Correct	124 ms	3148 KB	Output is correct
14	Correct	1086 ms	3156 KB	Output is correct
15	Execution timed out	5063 ms	3284 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-