Submission #1240819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240819		MateiKing80	Min-max tree (BOI18_minmaxtree)	C++20	0 / 100	116 ms	25636 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

const int N = 70005;
vector<int> vec[N];

vector<int> lazyMare[N];
set<int> setMare[N];
int lift[20][N], depth[N], mare[N];

void dfs(int nod, int papa) {
	depth[nod] = 1 + depth[papa];
	lift[0][nod] = papa;
	for (int bit = 1; bit < 20; bit ++)
		lift[bit][nod] = lift[bit - 1][lift[bit - 1][nod]];
	for (auto i : vec[nod])
		if (i != papa)
			dfs(i, nod);
}

int lca(int x, int y) {
	if (depth[x] > depth[y])
		swap(x, y);
	for (int bit = 19; bit >= 0; bit --)
		if (depth[lift[bit][y]] >= depth[x])
			y = lift[bit][y];
	if (x == y)
		return x;
	for (int bit = 19; bit >= 0; bit --)
		if (lift[bit][x] != lift[bit][y]) {
			x = lift[bit][x];
			y = lift[bit][y];
		}
	return lift[0][x];
}

void dfsMare(int nod, int papa) {
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		dfsMare(i, nod);
		if (setMare[nod].size() < setMare[i].size())
			swap(setMare[nod], setMare[i]);
		for (auto j : setMare[i])
			setMare[nod].insert(j);
		setMare[i].clear();
	}
	for (auto i : lazyMare[nod]) {
		if (i < 0)
			setMare[nod].erase(-i);
		else
			setMare[nod].insert(i);
	}
	if (setMare[nod].empty())
		mare[nod] = -1;
	else
		mare[nod] = *setMare[nod].rbegin();
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(1, 0);
	int q;
	cin >> q;
	while (q --) {
		char ch;
		int x, y, z;
		cin >> ch >> x >> y >> z;
		if (ch == 'M') {
			lazyMare[x].push_back(z);
			lazyMare[y].push_back(z);
			lazyMare[lca(x, y)].push_back(-z);
		}
	}
	dfsMare(1, 0);
	for (int i = 2; i <= n; i ++)
		cout << i << " " << lift[0][i] << " " << (mare[i] == -1 ? 69 : mare[i]) << '\n';
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42