Submission #978068

#	Time	Username	Problem	Language	Result	Execution time	Memory
978068		Kel_Mahmut	Min-max tree (BOI18_minmaxtree)	C++17	22 / 100	1091 ms	34716 KiB

minmaxtree

#include <bits/stdc++.h>
#define pb push_back
#define all(aa) aa.begin(), aa.end()
#define endl ("\n")
typedef long long ll;
using namespace std;

int n;
vector<vector<int>> g, dede;
vector<int> d, p;

struct DSU{
	int n;
	vector<int> ata, p;
	DSU(int n, vector<int> p) : n(n), ata(n), p(p) {
		for(int i = 0; i < n; i++) ata[i] = i;
	}

	void rem(int a){
		int par = find(p[a]);
		ata[a] = par;
	}

	int find(int a){
		if(a == -1) return -1;
		if(ata[a] == a) return a;
		return ata[a] = find(ata[a]);
	}
};

void dfs1(int u, int ata = -1){
	for(int go : g[u]){
		if(go == ata) continue;
		p[go] = u;
		d[go] = d[u] + 1;
		dfs1(go, u);
	}
}

const int logar = 32;
void build_lca(){
	dede.resize(n, vector<int>(logar));
	for(int i = 0; i < n; i++){
		dede[i][0] = p[i];
	}
	for(int k = 1; k < logar; k++){
		for(int i = 0; i < n; i++){
			if(dede[i][k - 1] == -1)
				dede[i][k] = -1;
			else
				dede[i][k] = dede[dede[i][k - 1]][k - 1];
		}
	}
}

int find_lca(int a, int b){
	if(d[a] < d[b]) swap(a, b);
	for(int k = logar - 1; k >= 0; k--){
		if((1<<k) & (d[a] - d[b])){
			a = dede[a][k];
		}
	}
	for(int k = logar - 1; k >= 0; k--){
		if(dede[a][k] != dede[b][k])
			a = dede[a][k], b = dede[b][k];
	}
	if(a == b) return a;
	return p[a];
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int m;
	cin >> n;
	g.resize(n);
	for(int i = 0; i < n -  1; i++){
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	d.resize(n), p.resize(n);
	dfs1(0);
	p[0] = -1;
	cin >> m;
	vector<array<int, 3>> MIN, MAX;
	for(int i = 0; i < m; i++){
		char c;
		cin >> c;
		int x, y, z;
		cin >> x >> y >> z;
		x--, y--;
		if(c == 'm')
			MIN.pb({z, x, y});
		else
			MAX.pb({z, x, y});
	}
	build_lca();
	sort(all(MIN));
	reverse(all(MIN));
	sort(all(MAX));
	DSU max_free(n, p), min_free(n, p);
	vector<int> max_val, min_val;
	vector<int> max_assigned(n, -1), min_assigned(n, -1);
	vector<set<int>> max_can_go, min_can_go;
	int c = 0;
	for(auto [z, x, y] : MAX){
		int lca = find_lca(x, y);
		max_val.pb(z);
		max_can_go.emplace_back();
		while(1){
			x = max_free.find(x);
			if(x == -1 || d[x] <= d[lca]) break;
			max_can_go[c].insert(x);
			max_free.rem(x);
			max_assigned[x] = c;
		}
		while(1){
			y = max_free.find(y);
			if(y == -1 || d[y] <= d[lca]) break;
			max_can_go[c].insert(y);
			max_free.rem(y);
			max_assigned[y] = c;
		}
		c++;
	}

	c = 0;
	for(auto [z, x, y] : MIN){
		int lca = find_lca(x, y);
		min_val.pb(z);
		min_can_go.emplace_back();
		while(1){
			x = min_free.find(x);
			if(x == -1 || d[x] <= d[lca]) break;
			min_can_go[c].insert(x);
			min_free.rem(x);
			min_assigned[x] = c;
		}
		while(1){
			y = min_free.find(y);
			if(y == -1 || d[y] <= d[lca]) break;
			min_can_go[c].insert(y);
			min_free.rem(y);
			min_assigned[y] = c;
		}
		c++;
	}
	vector<int> ans(n);
	vector<bool> answered(n);
	set<pair<int, int>> max_sets, min_sets;
	for(int i = 0; i < (int) max_can_go.size(); i++)
		max_sets.insert({max_can_go[i].size(), i});
	for(int i = 0; i < (int) min_can_go.size(); i++)
		min_sets.insert({min_can_go[i].size(), i});

	while(!max_sets.empty() || !min_sets.empty()){
		while(!max_sets.empty() && max_sets.begin()->first == 1){
			c = max_sets.begin()->second;
			auto it = max_can_go[c].begin();
			answered[*it] = 1;
			ans[*it] = max_val[c];
			int ind = min_assigned[*it];
			if(ind != -1){
				min_sets.erase({min_can_go[ind].size(), ind});
				min_can_go[ind].erase(*it);
				min_sets.insert({min_can_go[ind].size(), ind});
			}
			max_sets.erase(max_sets.begin());
		}

		while(!min_sets.empty() && min_sets.begin()->first == 1){
			c = min_sets.begin()->second;
			auto it = min_can_go[c].begin();
			answered[*it] = 1;
			ans[*it] = min_val[c];
			int ind = max_assigned[*it];
			if(ind != -1){
				max_sets.erase({max_can_go[ind].size(), ind});
				max_can_go[ind].erase(*it);
				max_sets.insert({min_can_go[ind].size(), ind});
			}
			min_sets.erase(min_sets.begin());
		}

		if(!max_sets.empty() && max_sets.begin()->first == 1)
			continue;

		if(!max_sets.empty()){
			c = max_sets.begin()->second;
			auto it = max_can_go[c].begin();
			answered[*it] = 1;
			ans[*it] = max_val[c];
			int ind = min_assigned[*it];
			if(ind != -1){
				min_sets.erase({min_can_go[ind].size(), ind});
				min_can_go[ind].erase(*it);
				min_sets.insert({min_can_go[ind].size(), ind});
			}
			max_sets.erase(max_sets.begin());
		}

		if(!min_sets.empty()){
			c = min_sets.begin()->second;
			auto it = min_can_go[c].begin();
			answered[*it] = 1;
			ans[*it] = min_val[c];
			int ind = max_assigned[*it];
			if(ind != -1){
				max_sets.erase({max_can_go[ind].size(), ind});
				max_can_go[ind].erase(*it);
				max_sets.insert({min_can_go[ind].size(), ind});
			}
			min_sets.erase(min_sets.begin());
		}
	}

	for(int i = 1; i < n; i++){
		cout << i + 1 << ' ' << p[i] + 1 << ' ';
		if(answered[i])
			cout << ans[i] << endl;
		else if(max_assigned[i] != -1){
			cout << max_val[max_assigned[i]] << endl;
		}
		else if(min_assigned[i] != -1){
			cout << min_val[min_assigned[i]] << endl;
		}
		else cout << 0 << endl;
	}

}

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