oj.uz

답안 #834639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834639 2023-08-22T16:20:50 Z Elias Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 4425 ms 345964 KB 
#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;
vector<vector<int>> pre;

struct Tree
{
	int n = 0;
	int level = 0;

	vector<int> subtree;
	vector<int> initial_parent;

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

	int timer = 0;
	int centroid = -1;
	unordered_set<int> nodes;

	SegTree pre_dist_seg;

	void spread(int i, int p = -1)
	{
		n++;
		nodes.insert(i);
		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[level][i] = timer++;
		pre_order.push_back(i);
		pre_dist[pre[level][i]] = d;

		int subtree_size = 1;

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

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

		subtree[pre[level][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, int level) : level(level)
	{
		spread(start);
		pre_dist = initial_parent = subtree = 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 (nodes.count(a) != 0 && nodes.count(b) != 0)
		{
			if (pre[level][a] > pre[level][b])
				swap(a, b);

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

			int old_weight = dist_lower - dist_upper;

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

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

		auto dist2 = pre_dist_seg.get(0, pre[level][bad_child]).first;
		auto dist3 = pre_dist_seg.get(pre[level][bad_child] + subtree[pre[level][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);
	pre = vector<vector<int>>(30, vector<int>(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, 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, subtrees[index].level + 1);
			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(new_tree));
			}
		}
	}

	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

diameter.cpp: In function 'int main()':
diameter.cpp:300: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]
  300 |  for (int i = 0; i < subtrees.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 17 ms 1748 KB Output is correct
20 Correct 24 ms 2004 KB Output is correct
21 Correct 23 ms 2132 KB Output is correct
22 Correct 27 ms 2516 KB Output is correct
23 Correct 36 ms 8928 KB Output is correct
24 Correct 47 ms 10848 KB Output is correct
25 Correct 65 ms 12196 KB Output is correct
26 Correct 73 ms 13824 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 340 KB Output is correct
5 Correct 47 ms 664 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 13 ms 596 KB Output is correct
11 Correct 64 ms 1028 KB Output is correct
12 Correct 4 ms 3152 KB Output is correct
13 Correct 4 ms 3152 KB Output is correct
14 Correct 6 ms 3152 KB Output is correct
15 Correct 20 ms 3152 KB Output is correct
16 Correct 82 ms 3528 KB Output is correct
17 Correct 75 ms 56824 KB Output is correct
18 Correct 77 ms 56776 KB Output is correct
19 Correct 76 ms 56756 KB Output is correct
20 Correct 100 ms 56788 KB Output is correct
21 Correct 212 ms 56804 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2132 KB Output is correct
2 Correct 30 ms 2276 KB Output is correct
3 Correct 146 ms 2416 KB Output is correct
4 Correct 283 ms 2764 KB Output is correct
5 Correct 44 ms 25660 KB Output is correct
6 Correct 94 ms 25652 KB Output is correct
7 Correct 324 ms 25868 KB Output is correct
8 Correct 669 ms 26212 KB Output is correct
9 Correct 207 ms 146852 KB Output is correct
10 Correct 348 ms 147036 KB Output is correct
11 Correct 812 ms 147152 KB Output is correct
12 Correct 1481 ms 147416 KB Output is correct
13 Correct 421 ms 310016 KB Output is correct
14 Correct 553 ms 310084 KB Output is correct
15 Correct 1159 ms 310332 KB Output is correct
16 Correct 1888 ms 310632 KB Output is correct
17 Correct 3364 ms 310640 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2808 ms 245716 KB Output is correct
2 Correct 2865 ms 252604 KB Output is correct
3 Correct 2763 ms 250644 KB Output is correct
4 Correct 2903 ms 253016 KB Output is correct
5 Correct 2757 ms 236552 KB Output is correct
6 Correct 2445 ms 158048 KB Output is correct
7 Correct 3855 ms 312188 KB Output is correct
8 Correct 3802 ms 312064 KB Output is correct
9 Correct 3743 ms 312320 KB Output is correct
10 Correct 3806 ms 310728 KB Output is correct
11 Correct 3667 ms 292204 KB Output is correct
12 Correct 3199 ms 189940 KB Output is correct
13 Correct 4054 ms 345772 KB Output is correct
14 Correct 3984 ms 345836 KB Output is correct
15 Correct 4065 ms 345792 KB Output is correct
16 Correct 4081 ms 344000 KB Output is correct
17 Correct 3898 ms 321652 KB Output is correct
18 Correct 3247 ms 202032 KB Output is correct
19 Correct 4019 ms 345964 KB Output is correct
20 Correct 4349 ms 345940 KB Output is correct
21 Correct 4115 ms 345876 KB Output is correct
22 Correct 4043 ms 343968 KB Output is correct
23 Correct 3918 ms 321580 KB Output is correct
24 Correct 3225 ms 201944 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 17 ms 1748 KB Output is correct
20 Correct 24 ms 2004 KB Output is correct
21 Correct 23 ms 2132 KB Output is correct
22 Correct 27 ms 2516 KB Output is correct
23 Correct 36 ms 8928 KB Output is correct
24 Correct 47 ms 10848 KB Output is correct
25 Correct 65 ms 12196 KB Output is correct
26 Correct 73 ms 13824 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 8 ms 340 KB Output is correct
31 Correct 47 ms 664 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 1 ms 596 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 13 ms 596 KB Output is correct
37 Correct 64 ms 1028 KB Output is correct
38 Correct 4 ms 3152 KB Output is correct
39 Correct 4 ms 3152 KB Output is correct
40 Correct 6 ms 3152 KB Output is correct
41 Correct 20 ms 3152 KB Output is correct
42 Correct 82 ms 3528 KB Output is correct
43 Correct 75 ms 56824 KB Output is correct
44 Correct 77 ms 56776 KB Output is correct
45 Correct 76 ms 56756 KB Output is correct
46 Correct 100 ms 56788 KB Output is correct
47 Correct 212 ms 56804 KB Output is correct
48 Correct 6 ms 2132 KB Output is correct
49 Correct 30 ms 2276 KB Output is correct
50 Correct 146 ms 2416 KB Output is correct
51 Correct 283 ms 2764 KB Output is correct
52 Correct 44 ms 25660 KB Output is correct
53 Correct 94 ms 25652 KB Output is correct
54 Correct 324 ms 25868 KB Output is correct
55 Correct 669 ms 26212 KB Output is correct
56 Correct 207 ms 146852 KB Output is correct
57 Correct 348 ms 147036 KB Output is correct
58 Correct 812 ms 147152 KB Output is correct
59 Correct 1481 ms 147416 KB Output is correct
60 Correct 421 ms 310016 KB Output is correct
61 Correct 553 ms 310084 KB Output is correct
62 Correct 1159 ms 310332 KB Output is correct
63 Correct 1888 ms 310632 KB Output is correct
64 Correct 3364 ms 310640 KB Output is correct
65 Correct 2808 ms 245716 KB Output is correct
66 Correct 2865 ms 252604 KB Output is correct
67 Correct 2763 ms 250644 KB Output is correct
68 Correct 2903 ms 253016 KB Output is correct
69 Correct 2757 ms 236552 KB Output is correct
70 Correct 2445 ms 158048 KB Output is correct
71 Correct 3855 ms 312188 KB Output is correct
72 Correct 3802 ms 312064 KB Output is correct
73 Correct 3743 ms 312320 KB Output is correct
74 Correct 3806 ms 310728 KB Output is correct
75 Correct 3667 ms 292204 KB Output is correct
76 Correct 3199 ms 189940 KB Output is correct
77 Correct 4054 ms 345772 KB Output is correct
78 Correct 3984 ms 345836 KB Output is correct
79 Correct 4065 ms 345792 KB Output is correct
80 Correct 4081 ms 344000 KB Output is correct
81 Correct 3898 ms 321652 KB Output is correct
82 Correct 3247 ms 202032 KB Output is correct
83 Correct 4019 ms 345964 KB Output is correct
84 Correct 4349 ms 345940 KB Output is correct
85 Correct 4115 ms 345876 KB Output is correct
86 Correct 4043 ms 343968 KB Output is correct
87 Correct 3918 ms 321580 KB Output is correct
88 Correct 3225 ms 201944 KB Output is correct
89 Correct 2847 ms 249340 KB Output is correct
90 Correct 3152 ms 274268 KB Output is correct
91 Correct 3651 ms 303904 KB Output is correct
92 Correct 3929 ms 312128 KB Output is correct
93 Correct 3966 ms 323448 KB Output is correct
94 Correct 3955 ms 330824 KB Output is correct
95 Correct 4056 ms 344172 KB Output is correct
96 Correct 4033 ms 344012 KB Output is correct
97 Correct 4045 ms 344212 KB Output is correct
98 Correct 4181 ms 345588 KB Output is correct
99 Correct 4425 ms 344080 KB Output is correct
100 Correct 4283 ms 344048 KB Output is correct