Submission #574566

#	Time	Username	Problem	Language	Result	Execution time	Memory
574566		FatihSolak	Min-max tree (BOI18_minmaxtree)	C++17	29 / 100	631 ms	98792 KiB

minmaxtree

#include <bits/stdc++.h>
#define N 200005
#define K 20
using namespace std;
vector<int> adj[N];
map<pair<int,int>,pair<int,int>> edge;
int par[N][K];
int dep[N];
set<int> s[N][2];
set<int> del[N][2];
map<int,bool> needed;
void dfs0(int v,int pr){
	par[v][0] = pr;
	dep[v] = dep[pr] + 1;
	for(auto u:adj[v]){
		if(u == pr)continue;
		dfs0(u,v);
	}
}
void dfs1(int v,int pr){
	for(auto u:adj[v]){
		if(u == pr)continue;
		dfs1(u,v);
		for(int i = 0;i<2;i++){
			if(s[u][i].size() > s[v][i].size()){
				swap(s[u][i],s[v][i]);
			}
			for(auto c:s[u][i]){
				s[v][i].insert(c);
			}
		}
	}
	for(int i = 0;i<2;i++){
		for(auto u:del[v][i]){
			s[v][i].erase(u);
		}
	}
	if(s[v][0].size()){
		edge[{min(v,pr),max(v,pr)}].first = max(edge[{min(v,pr),max(v,pr)}].first,*s[v][0].rbegin());
	}
	if(s[v][1].size()){
		edge[{min(v,pr),max(v,pr)}].second = min(edge[{min(v,pr),max(v,pr)}].second,*s[v][1].begin());
	}
}
int lca(int u,int v){
	if(dep[u] < dep[v])swap(u,v);
	for(int j = K-1;j>=0;j--){
		if(dep[par[u][j]] >= dep[v]){
			u = par[u][j];
		}
	}
	if(u == v)
		return u;
	for(int j = K-1;j>=0;j--){
		if(par[u][j] != par[v][j]){
			u = par[u][j];
			v = par[v][j];
		}
	}
	return par[u][0];
}
void solve(){
	int n;
	cin >> n;
	map<pair<int,int>,int> ans;
	for(int i = 1;i<n;i++){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edge[{min(u,v),max(u,v)}] = {-1,1e9 + 1};
		ans[{min(u,v),max(u,v)}] = 0;
	}
	dfs0(1,0);
	for(int j = 1;j<K;j++){
		for(int i = 1;i<=n;i++){
			par[i][j] = par[par[i][j-1]][j-1];
		}
	}
	int k;
	cin >> k;
	for(int i = 1;i<=k;i++){
		char type;
		int u,v,x;
		cin >> type >> u >> v >> x;
		needed[x] = 1;
		int lc = lca(u,v);
		if(type == 'M'){
			s[u][1].insert(x);
			s[v][1].insert(x);
			del[lc][1].insert(x);
		}
		if(type == 'm'){
			s[u][0].insert(x);
			s[v][0].insert(x);
			del[lc][0].insert(x);
		}
	}
	dfs1(1,0);
	map<int,set<pair<int,pair<int,int>>>> adj2;
	for(auto u:edge){
		if(needed[u.second.first]){
			adj2[u.second.first].insert({u.second.second,u.first});
		}
		if(needed[u.second.second]){
			adj2[u.second.second].insert({u.second.first,u.first});
		}
	}
	set<pair<int,int>> ss;
	for(auto u:adj2){
		ss.insert({u.second.size(),u.first});
	}
	while(ss.size()){
		int num = ss.begin()->second;
		ss.erase(ss.begin());
		needed[num] = 0;
		ans[adj2[num].begin()->second] = num;
		if(needed[adj2[num].begin()->first]){
			ss.erase({adj2[adj2[num].begin()->first].size(),adj2[num].begin()->first});
			adj2[adj2[num].begin()->first].erase({num,adj2[num].begin()->second});
			ss.insert({adj2[adj2[num].begin()->first].size(),adj2[num].begin()->first});
		}

	}
	for(auto u:ans){
		cout << u.first.first << " " << u.first.second << " "<< u.second << endl;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	#ifdef Local
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	#ifdef Local
		cout << endl << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds.";
	#endif
}

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