oj.uz

Submission #709751

# Submission time Handle Problem Language Result Execution time Memory
709751 2023-03-14T11:28:28 Z surgutti Min-max tree (BOI18_minmaxtree) C++14
22 / 100
 110 ms 19000 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 70000 + 11;
const int L = 17;

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];
int 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);
	}

	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

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 18540 KB Output is correct
2 Correct 98 ms 16236 KB Output is correct
3 Correct 84 ms 16424 KB Output is correct
4 Correct 110 ms 19000 KB Output is correct
5 Correct 90 ms 16448 KB Output is correct
6 Correct 101 ms 16596 KB Output is correct
7 Correct 87 ms 16116 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 12656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3540 KB Output isn't correct
2 Halted 0 ms 0 KB -