Submission #1263854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263854		4QT0R	Min-max tree (BOI18_minmaxtree)	C++20	0 / 100	96 ms	33348 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;

vector<int> tree[70002];
set<int> mn[70002];
set<int> mx[70002];
vector<array<int,3>> ans;
int par[70002];
pair<int,int> limits[70002];

int iter;
unordered_map<int, int> et;
int wart[140002];

/////////////////////////////////////////////////////////
vector<int> graph[140003];
int vis[140003];
int timer;
int match[140003];

bool update(int v){
	vis[v]=timer;
	for (auto u : graph[v]){
		if (match[u]==-1){
			match[v]=u;
			match[u]=v;
			return true;
		}
	}
	for (auto u : graph[v]){
		if (vis[match[u]]!=timer && update(match[u])){
			match[v]=u;
			match[u]=v;
			return true;
		}
	}
	return false;
}

void turbo_matching(int n){
	fill(match, match+n+1, -1);
	while(true){
		timer++;
		bool any=false;
		for (int i = 1; i<=n; i++){
			if (match[i]==-1 && update(i)){
				any=true;
			}
		}
		if (!any)return;
	}
}
////////////////////////////////////////////////////////////

void dfs(int v, int p){
	par[v]=p;
	for (auto u : tree[v]){
		if (u==p)continue;
		dfs(u,v);
		if (mn[u].size() > mn[v].size())swap(mn[u],mn[v]);
		if (mx[u].size() > mx[v].size())swap(mx[u],mx[v]);
		for (auto x : mn[u]){
			if (mn[v].count(x))mn[v].erase(x);
			else mn[v].insert(x);
		}
		for (auto x : mx[u]){
			if (mx[v].count(x))mx[v].erase(x);
			else mx[v].insert(x);
		}
	}
	if (mn[v].size()){
		int x = *mn[v].begin();
		if (!et[x]){
			et[x]=++iter;
			wart[iter]=x;
		}
		graph[v].push_back(et[x]);
		graph[et[x]].push_back(v);
		limits[v].first=x;
	}
	if (mx[v].size()){
		int x = *mx[v].rbegin();
		if (!et[x]){
			et[x]=++iter;
			wart[iter]=x;
		}
		graph[v].push_back(et[x]);
		graph[et[x]].push_back(v);
		limits[v].second=x;
	}
	// cout << v << ' ' << par[v] << '\n';
	// cout << limits[v].first << ' ' << limits[v].second << '\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,k;
	cin >> n;
	for (int i = 1,a,b; i<n; i++){
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	cin >> k;
	char zn;
	for (int i = 1, a, b, c; i<=k; i++){
		cin >> zn >> a >> b >> c;
		if (zn=='m'){
			mn[a].insert(c);
			mn[b].insert(c);
		}
		else{
			mx[a].insert(c);
			mx[b].insert(c);
		}
	}
	iter = n;
	dfs(1,0);
	turbo_matching(iter);
	for (int i = 2; i<=n; i++){
		if (match[i]!=-1)
			cout << i << ' ' << par[i] << ' ' << wart[match[i]] << '\n';
		else
			cout << i << ' ' << par[i] << ' ' << (limits[i].first^limits[i].second) << '\n';
	}

}
/*
4
1 2
2 3
3 4
3
M 1 2 1
m 1 4 0
M 2 3 100
*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42