oj.uz

Submission #709757

# Submission time Handle Problem Language Result Execution time Memory
709757 2023-03-14T11:35:34 Z surgutti Min-max tree (BOI18_minmaxtree) C++17
22 / 100
 113 ms 20436 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 70000 + 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++;
			assert(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';
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 7124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 16720 KB Output is correct
2 Correct 90 ms 14368 KB Output is correct
3 Correct 93 ms 14992 KB Output is correct
4 Correct 113 ms 17340 KB Output is correct
5 Correct 105 ms 14856 KB Output is correct
6 Correct 94 ms 14872 KB Output is correct
7 Correct 80 ms 14252 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 20436 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 7124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -