oj.uz

Submission #365283

# Submission time Handle Problem Language Result Execution time Memory
365283 2021-02-11T11:25:32 Z kostia244 Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 318 ms 38116 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 70100;
void bad() {
	exit(42);
}
int n, k, m, p[maxn];
vector<int> g[maxn];
vector<int> add[maxn];
array<int, 2> range[maxn];
set<int> L[maxn], H[maxn];
void dfs(int v) {
	range[v] = {-(1<<30), 1<<30};
	auto add_mx = [&](int i) {
		if(!H[v].insert(i).second) H[v].erase(i);
	};
	auto add_mn = [&](int i) {
		if(!L[v].insert(i).second) L[v].erase(i);
	};
	for(auto &i : g[v]) {
		p[i] = v;
		g[i].erase(find(all(g[i]), v));
		dfs(i);
		if(L[i].size()+H[i].size() > L[v].size()+H[v].size())
			swap(L[i], L[v]), swap(H[i], H[v]);
	}
	for(auto &i : g[v]) {
		for(auto &x : L[i])
			add_mn(x);
		for(auto &x : H[i])
			add_mx(x);
	}
	for(auto i : add[v]) {
		if(i < 0) add_mx(-i);
		else add_mn(i);
	}
	if(L[v].size()) range[v][0] = *L[v].rbegin();
	if(H[v].size()) range[v][1] = *H[v].begin();
	//for(auto i : L[v]) cout << i << " ";cout << " | " << v << endl;
}
vector<int> vals, dead, ans, deg, used;
vector<array<int, 2>> cg[maxn];
void add_edge(int u, int v, int id) {
	cg[u].push_back({v, id});
	cg[v].push_back({u, id});
	//cout << u << " " << v << " " << id << endl;
}
void add_loop(int u, int id) {
	add_edge(u, u, id);
}
set<array<int, 2>> q;
void kill_edge(int u, int v, int id) {
	dead[id] = 1;
	ans[id] = u;
	q.erase({deg[u], u});
	used[u] = 1;
	if(!used[v]) {
		q.erase({deg[v], v});
		q.insert({--deg[v], v});
	}
}
void solve() {
	m = vals.size();
	dead.resize(n+1);
	used.resize(n+1);
	ans.resize(n+1, -1);
	deg.resize(m);
	for(int i = 0; i < m; i++) q.insert({deg[i] = cg[i].size(), i});
	while(!q.empty()) {
		auto v = q.begin()->at(1);
		//cout << "sat " << v << " "<< deg[v] << endl;
		if(deg[v] == 0) bad();
		for(auto [dest, id] : cg[v]) if(!dead[id]) {
			kill_edge(v, dest, id);
			break;
		}

	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	//multitest([&](){});
	cin >> n;
	for(int f, t, i = 1; i < n; i++) {
		cin >> f >> t;
		g[f].push_back(t);
		g[t].push_back(f);
	}
	int u, v, x;
	char c;
	cin >> k;
	for(int q = 0; q < k; q++) {
		cin >> c >> u >> v >> x;
		vals.push_back(x);
		if(c == 'M') x *= -1;
		add[u].push_back(x);
		add[v].push_back(x);
	}
	dfs(1);
	sort(all(vals));
	vals.erase(unique(all(vals)), vals.end());
	for(int i = 2; i <= n; i++) {
		int l = range[i][0], r = range[i][1];
		if(l > r) bad();
		//cout << i << " " << l << " " << r << endl;
		if(l >= 0) l = lower_bound(all(vals), l) - vals.begin();
		if(r != 1<<30) r = lower_bound(all(vals), r) - vals.begin();
		if(l >= 0 && r != 1<<30) {
			add_edge(l, r, i);
		} else if(l >= 0 || r != 1<<30) {
			add_loop(l >= 0 ? l : r, i);
		}
	}
	solve();
	for(int i = 2; i <= n; i++) {
		if(ans[i] == -1) ans[i] = max(0, range[i][0]);
		else ans[i] = vals[ans[i]];
		cout << i << " " << p[i] << " " << ans[i] << '\n';
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11884 KB Output is correct
2 Correct 8 ms 11884 KB Output is correct
3 Correct 8 ms 11884 KB Output is correct
4 Correct 8 ms 11884 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 31204 KB Output is correct
2 Correct 226 ms 34020 KB Output is correct
3 Correct 214 ms 29416 KB Output is correct
4 Correct 236 ms 31360 KB Output is correct
5 Correct 213 ms 30568 KB Output is correct
6 Correct 212 ms 28132 KB Output is correct
7 Correct 195 ms 26488 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 22636 KB Output is correct
2 Correct 127 ms 24172 KB Output is correct
3 Correct 148 ms 25708 KB Output is correct
4 Correct 115 ms 27628 KB Output is correct
5 Correct 142 ms 24428 KB Output is correct
6 Correct 149 ms 25196 KB Output is correct
7 Correct 144 ms 23788 KB Output is correct
8 Correct 147 ms 23776 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11884 KB Output is correct
2 Correct 8 ms 11884 KB Output is correct
3 Correct 8 ms 11884 KB Output is correct
4 Correct 8 ms 11884 KB Output is correct
5 Correct 236 ms 31204 KB Output is correct
6 Correct 226 ms 34020 KB Output is correct
7 Correct 214 ms 29416 KB Output is correct
8 Correct 236 ms 31360 KB Output is correct
9 Correct 213 ms 30568 KB Output is correct
10 Correct 212 ms 28132 KB Output is correct
11 Correct 195 ms 26488 KB Output is correct
12 Correct 153 ms 22636 KB Output is correct
13 Correct 127 ms 24172 KB Output is correct
14 Correct 148 ms 25708 KB Output is correct
15 Correct 115 ms 27628 KB Output is correct
16 Correct 142 ms 24428 KB Output is correct
17 Correct 149 ms 25196 KB Output is correct
18 Correct 144 ms 23788 KB Output is correct
19 Correct 147 ms 23776 KB Output is correct
20 Correct 285 ms 38116 KB Output is correct
21 Correct 248 ms 35432 KB Output is correct
22 Correct 318 ms 36584 KB Output is correct
23 Correct 271 ms 35048 KB Output is correct
24 Correct 298 ms 32740 KB Output is correct
25 Correct 301 ms 35672 KB Output is correct
26 Correct 259 ms 34408 KB Output is correct
27 Correct 273 ms 32996 KB Output is correct
28 Correct 278 ms 31976 KB Output is correct
29 Correct 259 ms 32484 KB Output is correct
30 Correct 234 ms 31592 KB Output is correct
31 Correct 255 ms 31848 KB Output is correct
32 Correct 280 ms 32640 KB Output is correct
33 Correct 265 ms 33640 KB Output is correct
34 Correct 271 ms 33560 KB Output is correct
35 Correct 245 ms 31336 KB Output is correct