oj.uz

Submission #68284

# Submission time Handle Problem Language Result Execution time Memory
68284 2018-08-16T11:12:34 Z aome Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 786 ms 96312 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13560 KB Output is correct
2 Correct 13 ms 13796 KB Output is correct
3 Correct 13 ms 13796 KB Output is correct
4 Correct 14 ms 13796 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 41032 KB Output is correct
2 Correct 507 ms 43180 KB Output is correct
3 Correct 408 ms 43180 KB Output is correct
4 Correct 736 ms 48672 KB Output is correct
5 Correct 689 ms 48672 KB Output is correct
6 Correct 726 ms 49756 KB Output is correct
7 Correct 690 ms 50908 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 50908 KB Output is correct
2 Correct 296 ms 50908 KB Output is correct
3 Correct 312 ms 50908 KB Output is correct
4 Correct 320 ms 50908 KB Output is correct
5 Correct 370 ms 50908 KB Output is correct
6 Correct 418 ms 50908 KB Output is correct
7 Correct 327 ms 50908 KB Output is correct
8 Correct 425 ms 52236 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13560 KB Output is correct
2 Correct 13 ms 13796 KB Output is correct
3 Correct 13 ms 13796 KB Output is correct
4 Correct 14 ms 13796 KB Output is correct
5 Correct 545 ms 41032 KB Output is correct
6 Correct 507 ms 43180 KB Output is correct
7 Correct 408 ms 43180 KB Output is correct
8 Correct 736 ms 48672 KB Output is correct
9 Correct 689 ms 48672 KB Output is correct
10 Correct 726 ms 49756 KB Output is correct
11 Correct 690 ms 50908 KB Output is correct
12 Correct 261 ms 50908 KB Output is correct
13 Correct 296 ms 50908 KB Output is correct
14 Correct 312 ms 50908 KB Output is correct
15 Correct 320 ms 50908 KB Output is correct
16 Correct 370 ms 50908 KB Output is correct
17 Correct 418 ms 50908 KB Output is correct
18 Correct 327 ms 50908 KB Output is correct
19 Correct 425 ms 52236 KB Output is correct
20 Correct 593 ms 67704 KB Output is correct
21 Correct 523 ms 67704 KB Output is correct
22 Correct 535 ms 70600 KB Output is correct
23 Correct 571 ms 70600 KB Output is correct
24 Correct 707 ms 76240 KB Output is correct
25 Correct 747 ms 80548 KB Output is correct
26 Correct 665 ms 80756 KB Output is correct
27 Correct 710 ms 82984 KB Output is correct
28 Correct 721 ms 82984 KB Output is correct
29 Correct 649 ms 85112 KB Output is correct
30 Correct 625 ms 85112 KB Output is correct
31 Correct 786 ms 88116 KB Output is correct
32 Correct 726 ms 92012 KB Output is correct
33 Correct 642 ms 94404 KB Output is correct
34 Correct 604 ms 96312 KB Output is correct
35 Correct 610 ms 96312 KB Output is correct