제출 #365283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365283		kostia244	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	318 ms	38116 KiB

minmaxtree

#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 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42