Submission #861409

#	Time	Username	Problem	Language	Result	Execution time	Memory
861409		iskhakkutbilim	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	1054 ms	15440 KiB

minmaxtree

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

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
const int N = 1e5;


struct edge{
	int a, b, w;
};
int n;
vector<pair<int, int> > g[N+10];
pair<int, int> value[N + 10], E[N + 10];
int ans[N + 10];
vector<int> ve, ve1;
void dfs(int v, int par, int dest){
	if(v == dest){
		ve1 = ve;
		return;
	}
	for(auto [to, idx] : g[v]){
		if(to == par) continue;
		ve.push_back(idx);
		dfs(to, v, dest);
		ve.pop_back();
	}
}

/*
11
1 3
1 2
1 5
3 4
2 6
2 7
5 11
7 8
8 9
8 10
2
M 1 10 50
m 1 2 1
*/



main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1;i < n; i++){
		value[i] = {-1, -1};
		ans[i] = -1;
		int a, b; cin >> a >> b;
		E[i] = {a, b};
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	int q; cin >> q;
	vector<edge> high, low;
	set<int> W;
	for(int i = 0;i < q; i++){
		char ch; cin >> ch;
		int a, b, w; cin >> a >> b >> w;
		W.insert(w);
		if(ch == 'M') high.push_back({a, b, w});
		else low.push_back({a, b, w});
	}
	if(W.size() != q) assert(false);
	sort(all(low), [&](edge A, edge B){
		return A.w > B.w;	
	});
	sort(all(high), [&](edge A, edge B){
		return A.w < B.w;	
	});
	for(auto [a, b, w] : low){
		ve.clear();
		ve1.clear();
		dfs(a, a, b);
		for(int idx : ve1){
			if(value[idx].ff == -1 or value[idx].ff < w)  value[idx].ff = w;
		}
	}
	
	for(auto [a, b, w] : high){
		ve.clear();
		ve1.clear();
		dfs(a, a, b);
		for(int idx : ve1){
			if(value[idx].ss == -1 or value[idx].ss > w)  value[idx].ss = w;
		}
	}
	set<int> st;
	for(int i = 1;i < n; i++){
		if(value[i].ff != -1 && st.count(value[i].ff) == false){
			st.insert(value[i].ff);
			ans[i] = value[i].ff;
		}else if(value[i].ss != -1 && st.count(value[i].ss) == false){
			st.insert(value[i].ss);
			ans[i] = value[i].ss;
		}
	}
	for(int i = 1;i < n; i++){
		if(ans[i] == -1){
			for(int k = (value[i].ff == -1 ? 0 : value[i].ff); k <= (value[i].ss == -1 ? N :value[i].ss); k++){
				ans[i] = k;
			}
		}
	}
	for(int i = 1;i < n; i++){
		if(ans[i] == -1) assert(false);
		cout << E[i].ff << ' ' << E[i].ss << ' ';
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message (stderr)

minmaxtree.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:73:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  if(W.size() != q) assert(false);
      |     ~~~~~~~~~^~~~

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