Submission #68284

#	Time	Username	Problem	Language	Result	Execution time	Memory
68284		aome	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	786 ms	96312 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

const int N = 70005;

int n, m;
int deg[N];
int w[N], a[2][N];
int h[N], p[20][N];
int match[N];
bool visit[N];
vector<int> G[N];
set< pair<int, int> > s[2][N];
vector< pair<int, int> > vec[2][N];
vector<int> G2[N];
set< pair<int, int> > s2;

void dfs(int u) {
	for (int i = 1; i <= 17; ++i) {
		p[i][u] = p[i - 1][p[i - 1][u]];
	}
	for (auto v : G[u]) if (v != p[0][u]) {
		p[0][v] = u, h[v] = h[u] + 1, dfs(v);
	}
}

int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	for (int i = 17; i >= 0; --i) if (h[p[i][v]] >= h[u]) v = p[i][v];
	for (int i = 17; i >= 0; --i) if (p[i][v] != p[i][u]) v = p[i][v], u = p[i][u];
	return (u == v) ? u : p[0][u];
}

void dfs2(int u) {
	for (auto v : G[u]) if (v != p[0][u]) dfs2(v);
	for (int i = 0; i < 2; ++i) {
		int c = 0;
		for (auto v : G[u]) if (v != p[0][u]) {
			if (!c || s[i][v].size() > s[i][c].size()) c = v;
		}
		if (c) swap(s[i][u], s[i][c]);
		for (auto v : G[u]) if (v != p[0][u]) {
			for (auto j : s[i][v]) s[i][u].insert(j);
		}
		for (auto j : vec[i][u]) s[i][u].erase(j);
	}
	if (s[0][u].size()) {
		a[0][u] = s[0][u].rbegin() -> second, G2[a[0][u]].push_back(u);
	}
	if (s[1][u].size()) {
		a[1][u] = s[1][u].begin() -> second, G2[a[1][u]].push_back(u);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	p[0][1] = 1, dfs(1);
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		char type;
		int u, v; 
		cin >> type >> u >> v >> w[i];
		bool t = type == 'M';
		int tmp = lca(u, v);
		s[t][u].insert({w[i], i});
		s[t][v].insert({w[i], i});
		vec[t][tmp].push_back({w[i], i});
	}
	dfs2(1);
	for (int i = 1; i <= m; ++i) {
		deg[i] = G2[i].size(), s2.insert({deg[i], i});
	}
	while (s2.size()) {
		int id = s2.begin() -> second; s2.erase(s2.begin());
		int u = 0;
		for (auto j : G2[id]) {
			if (!match[j]) { u = j; break; } 
		}
		match[u] = id, visit[id] = 1;
		if (a[0][u] && a[1][u]) {
			id ^= a[0][u] ^ a[1][u];
			if (!visit[id]) {
				s2.erase({deg[id]--, id});
				s2.insert({deg[id], id});
			}
		}
	}
	for (int i = 2; i <= n; ++i) {
		cout << i << ' ' << p[0][i] << ' ';
		if (match[i]) cout << w[match[i]] << '\n';
		else cout << w[a[0][i]] << '\n';
	}
}

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