oj.uz

Submission #834555

# Submission time Handle Problem Language Result Execution time Memory
834555 2023-08-22T15:26:01 Z Elias Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 5000 ms 554256 KB 
#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
{
	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));
	}
};

struct Tree
{
	int n;

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

	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;

	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_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] : 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)
		{
			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, 0ll});
	}
};

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

	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) % (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

diameter.cpp: In function 'int main()':
diameter.cpp:299:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  299 |  for (int i = 0; i < subtrees.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
diameter.cpp: In constructor 'Tree::Tree(std::unordered_map<long long int, std::vector<std::pair<long long int, long long int> > >)':
diameter.cpp:206:16: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  206 |   find_centroid(start);
      |   ~~~~~~~~~~~~~^~~~~~~

Subtask #1
11.0 / 11.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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 436 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct

Subtask #2
13.0 / 13.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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 436 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 44 ms 2648 KB Output is correct
20 Correct 35 ms 2972 KB Output is correct
21 Correct 40 ms 3284 KB Output is correct
22 Correct 46 ms 3956 KB Output is correct
23 Correct 87 ms 14096 KB Output is correct
24 Correct 89 ms 17724 KB Output is correct
25 Correct 102 ms 20148 KB Output is correct
26 Correct 122 ms 23568 KB Output is correct

Subtask #3
7.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 4 ms 340 KB Output is correct
4 Correct 35 ms 468 KB Output is correct
5 Correct 175 ms 1432 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 44 ms 852 KB Output is correct
11 Correct 200 ms 1928 KB Output is correct
12 Correct 6 ms 3540 KB Output is correct
13 Correct 9 ms 3520 KB Output is correct
14 Correct 11 ms 3540 KB Output is correct
15 Correct 51 ms 3668 KB Output is correct
16 Correct 228 ms 4508 KB Output is correct
17 Correct 122 ms 64712 KB Output is correct
18 Correct 120 ms 64564 KB Output is correct
19 Correct 125 ms 64624 KB Output is correct
20 Correct 177 ms 64836 KB Output is correct
21 Correct 399 ms 64824 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3412 KB Output is correct
2 Correct 55 ms 3540 KB Output is correct
3 Correct 251 ms 4120 KB Output is correct
4 Correct 548 ms 4772 KB Output is correct
5 Correct 112 ms 43644 KB Output is correct
6 Correct 193 ms 43804 KB Output is correct
7 Correct 537 ms 44436 KB Output is correct
8 Correct 1000 ms 45240 KB Output is correct
9 Correct 682 ms 258108 KB Output is correct
10 Correct 846 ms 258260 KB Output is correct
11 Correct 1467 ms 258932 KB Output is correct
12 Correct 2319 ms 259780 KB Output is correct
13 Correct 1438 ms 549648 KB Output is correct
14 Correct 1661 ms 549820 KB Output is correct
15 Correct 2486 ms 550556 KB Output is correct
16 Correct 3415 ms 551284 KB Output is correct
17 Execution timed out 5048 ms 551184 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4411 ms 422632 KB Output is correct
2 Correct 4523 ms 435916 KB Output is correct
3 Correct 4620 ms 432700 KB Output is correct
4 Correct 4609 ms 438792 KB Output is correct
5 Correct 4245 ms 405076 KB Output is correct
6 Correct 3677 ms 255248 KB Output is correct
7 Execution timed out 5068 ms 554256 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 1 ms 352 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 436 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 44 ms 2648 KB Output is correct
20 Correct 35 ms 2972 KB Output is correct
21 Correct 40 ms 3284 KB Output is correct
22 Correct 46 ms 3956 KB Output is correct
23 Correct 87 ms 14096 KB Output is correct
24 Correct 89 ms 17724 KB Output is correct
25 Correct 102 ms 20148 KB Output is correct
26 Correct 122 ms 23568 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 4 ms 340 KB Output is correct
30 Correct 35 ms 468 KB Output is correct
31 Correct 175 ms 1432 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 6 ms 596 KB Output is correct
36 Correct 44 ms 852 KB Output is correct
37 Correct 200 ms 1928 KB Output is correct
38 Correct 6 ms 3540 KB Output is correct
39 Correct 9 ms 3520 KB Output is correct
40 Correct 11 ms 3540 KB Output is correct
41 Correct 51 ms 3668 KB Output is correct
42 Correct 228 ms 4508 KB Output is correct
43 Correct 122 ms 64712 KB Output is correct
44 Correct 120 ms 64564 KB Output is correct
45 Correct 125 ms 64624 KB Output is correct
46 Correct 177 ms 64836 KB Output is correct
47 Correct 399 ms 64824 KB Output is correct
48 Correct 12 ms 3412 KB Output is correct
49 Correct 55 ms 3540 KB Output is correct
50 Correct 251 ms 4120 KB Output is correct
51 Correct 548 ms 4772 KB Output is correct
52 Correct 112 ms 43644 KB Output is correct
53 Correct 193 ms 43804 KB Output is correct
54 Correct 537 ms 44436 KB Output is correct
55 Correct 1000 ms 45240 KB Output is correct
56 Correct 682 ms 258108 KB Output is correct
57 Correct 846 ms 258260 KB Output is correct
58 Correct 1467 ms 258932 KB Output is correct
59 Correct 2319 ms 259780 KB Output is correct
60 Correct 1438 ms 549648 KB Output is correct
61 Correct 1661 ms 549820 KB Output is correct
62 Correct 2486 ms 550556 KB Output is correct
63 Correct 3415 ms 551284 KB Output is correct
64 Execution timed out 5048 ms 551184 KB Time limit exceeded
65 Halted 0 ms 0 KB -