Submission #709770

#	Time	Username	Problem	Language	Result	Execution time	Memory
709770		surgutti	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	105 ms	21748 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

const int N = 100000 + 11;

int n, k;
vector<pair<int, int>> adj[N];
vector<pair<int, int>> edges;
int par[N], jmp[N], dep[N];

void dfs(int u, int f) {
	jmp[u] = f;

	for (auto [v, id] : adj[u]) if (v != f) {
		par[v] = id;
		dep[v] = dep[u] + 1;
		dfs(v, u);
	}
}

int uf[N];

int get(int u) {
	return u == uf[u] ? u : uf[u] = get(uf[u]);
}

int mn[N], mx[N];

vector<int> adj_mat[N];

void jazda(int u, int v, int id, int val) {
	u = get(u);
	v = get(v);

	while (u != v) {

		if (dep[u] < dep[v])
			swap(u, v);

		if (val > 0)
			mx[par[u]] = + val;
		else
			mn[par[u]] = - val;

		adj_mat[id].push_back(par[u]);

		uf[u] = get(jmp[u]);
		
		u = get(u);
	}
}

int mat[N], vis[N], col = 1;

bool match(int u) {
	if (vis[u] == col)
		return false;
	vis[u] = col;

	for (int v : adj_mat[u])
		if (mat[v] == -1)
			return mat[v] = u, true;
	
	for (int v : adj_mat[u])
		if (match(mat[v]))
			return mat[v] = u, true;

	return false;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int u, v; cin >> u >> v;

		adj[u].emplace_back(v, i);
		adj[v].emplace_back(u, i);

		edges.emplace_back(u, v);
	}

	par[1] = -1;
	dfs(1, 1);

	cin >> k;

	vector<tuple<int, int, int, int>> mini, maxi;
	vector<int> values;
	for (int i = 0; i < k; i++) {
		char c; int u, v, z; cin >> c >> u >> v >> z;

		values.push_back(z);

		if (c == 'm')
			mini.emplace_back(- z, u, v, i);
		else
			maxi.emplace_back(+ z, u, v, i);
	}

	for (int i = 0; i < n - 1; i++)
		mn[i] = mx[i] = 1;

	sort(mini.begin(), mini.end());
	sort(maxi.begin(), maxi.end());

	for (int i = 1; i <= n; i++)
		uf[i] = i;

	for (auto [z, u, v, i] : mini)
		jazda(u, v, i, z);

	for (int i = 1; i <= n; i++)
		uf[i] = i;

	for (auto [z, u, v, i] : maxi)
		jazda(u, v, i, z);

	for (int i = 0; i < k; i++) {
		vector<int> new_adj;

		for (int u : adj_mat[i])
			if (mn[u] <= values[i] && values[i] <= mx[u])
				new_adj.push_back(u);

		// swap(new_adj, adj_mat[i]);
	}

	for (int i = 0; i < n - 1; i++)
		mat[i] = -1;

	for (int i = 0; i < k; i++) {
		if (!match(i)) {
			col++;
			match(i);
		}
	}

	for (int i = 0; i < n - 1; i++) {
		auto [u, v] = edges[i];
		
		if (mat[i] == -1)
			cout << u << ' ' << v << ' ' << mn[i] << '\n';
		else
			cout << u << ' ' << v << ' ' << values[mat[i]] << '\n';
	}
}

Compilation message (stderr)

minmaxtree.cpp: In function 'void dfs(int, int)':
minmaxtree.cpp:15:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |  for (auto [v, id] : adj[u]) if (v != f) {
      |            ^
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:113:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |  for (auto [z, u, v, i] : mini)
      |            ^
minmaxtree.cpp:119:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |  for (auto [z, u, v, i] : maxi)
      |            ^
minmaxtree.cpp:143:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  143 |   auto [u, v] = edges[i];
      |        ^

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