oj.uz

답안 #834478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834478 2023-08-22T14:47:27 Z Elias Dynamic Diameter (CEOI19_diameter) C++17
0 / 100
 5000 ms 321200 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
{
	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)
		{
			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));
		}

		for (int i : trees_using[b])
		{
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 300 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 7 ms 212 KB Output is correct
4 Correct 63 ms 340 KB Output is correct
5 Correct 309 ms 640 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 14 ms 584 KB Output is correct
9 Correct 125 ms 572 KB Output is correct
10 Correct 1271 ms 768 KB Output is correct
11 Execution timed out 5018 ms 932 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5113 ms 321200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
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 1 ms 300 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -