Submission #574564

#	Time	Username	Problem	Language	Result	Execution time	Memory
574564		FatihSolak	Min-max tree (BOI18_minmaxtree)	C++17	7 / 100	135 ms	67132 KiB

minmaxtree

#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> adj[N];
map<pair<int,int>,pair<int,int>> edge;
vector<pair<int,pair<int,int>>> edges[N];
int timer = 1;
int tin[N];
int par[N];
int tout[N];
bool needed[N];
void dfs(int v,int pr){
	tin[v] = timer++;
	par[v] = pr;
	for(auto u:adj[v]){
		if(u == pr)continue;
		dfs(u,v);
	}
	tout[v] = timer - 1;
}
	vector<int> ret;
vector<int> get_path(int u,int v){
	vector<int> ret;
	while(tin[v] < tin[u] || tout[u] < tin[v]){
		ret.push_back(u);
		u = par[u];
	}
	vector<int> ret2;
	while(1){
		ret2.push_back(v);
		if(v == u)break;	
		v = par[v];
	}
	for(int i = ret2.size()-1;i>=0;i--)
		ret.push_back(ret2[i]);
	return ret;
}
set<pair<int,pair<int,int>>> adj2[N];
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,1001};
		ans[{min(u,v),max(u,v)}] = 0;
	}
	dfs(1,0);
	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;
		auto path = get_path(u,v);
		if(type == 'M'){
			for(int j = 1;j<(int)path.size();j++){
				pair<int,int> tmp = {min(path[j-1],path[j]),max(path[j-1],path[j])};
				edge[tmp].second = min(edge[tmp].second,x);
			}
		}
		if(type == 'm'){
			for(int j = 1;j<(int)path.size();j++){
				pair<int,int> tmp = {min(path[j-1],path[j]),max(path[j-1],path[j])};
				edge[tmp].first = max(edge[tmp].first,x);
			}
		}
	}
	for(auto u:edge){
		if(u.second.first != -1){
			adj2[u.second.first].insert({u.second.second,u.first});
		}
		if(u.second.first != 1001){
			adj2[u.second.second].insert({u.second.first,u.first});
		}
	}
	while(1){
		int mini = 1e9;
		int num = -1;
		for(int i = 0;i<=1000;i++){
			if(!needed[i])continue;
			mini = min(mini,(int)adj2[i].size());
			if((int)adj2[i].size() == mini){
				num = i;
			}
		}
		if(num == -1)break;
		needed[num] = 0;
		ans[adj2[num].begin()->second] = num;
		if(adj2[num].begin()->first != -1 && adj2[num].begin()->first != 1001){
			adj2[adj2[num].begin()->first].erase({num,adj2[num].begin()->second});
		}
	}
	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: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42