oj.uz

Submission #574574

# Submission time Handle Problem Language Result Execution time Memory
574574 2022-06-08T20:53:18 Z FatihSolak Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 850 ms 75076 KB 
#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;
set<int> s[N][2];
map<int,bool> needed;
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]){
				if(s[v][i].count(c))s[v][i].erase(c);
				else s[v][i].insert(c);
			}
		}
	}
	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());
	}
}
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)}] = {-2e9,2e9};
		ans[{min(u,v),max(u,v)}] = 2e9;
	}
	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;
		if(type == 'M'){
			s[u][1].insert(x);
			s[v][1].insert(x);
		}
		if(type == 'm'){
			s[u][0].insert(x);
			s[v][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});
		}

	}
	assert(ans.size() == n-1);
	for(auto u:needed){
		assert(u.second == 0); 
	}
	for(auto u:ans){
		if(u.second == 2e9){
			u.second = edge[u.first].first;
		}
		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
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from minmaxtree.cpp:1:
minmaxtree.cpp: In function 'void solve()':
minmaxtree.cpp:84:20: warning: comparison of integer expressions of different signedness: 'std::map<std::pair<int, int>, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |  assert(ans.size() == n-1);
      |         ~~~~~~~~~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 23 ms 23764 KB Output is correct
4 Correct 15 ms 23756 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 67488 KB Output is correct
2 Correct 545 ms 64628 KB Output is correct
3 Correct 503 ms 61528 KB Output is correct
4 Correct 632 ms 68764 KB Output is correct
5 Correct 547 ms 63060 KB Output is correct
6 Correct 563 ms 61512 KB Output is correct
7 Correct 512 ms 56668 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 45764 KB Output is correct
2 Correct 358 ms 46028 KB Output is correct
3 Correct 373 ms 50448 KB Output is correct
4 Correct 340 ms 53604 KB Output is correct
5 Correct 368 ms 48052 KB Output is correct
6 Correct 404 ms 49624 KB Output is correct
7 Correct 416 ms 47276 KB Output is correct
8 Correct 392 ms 46940 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 23 ms 23764 KB Output is correct
4 Correct 15 ms 23756 KB Output is correct
5 Correct 568 ms 67488 KB Output is correct
6 Correct 545 ms 64628 KB Output is correct
7 Correct 503 ms 61528 KB Output is correct
8 Correct 632 ms 68764 KB Output is correct
9 Correct 547 ms 63060 KB Output is correct
10 Correct 563 ms 61512 KB Output is correct
11 Correct 512 ms 56668 KB Output is correct
12 Correct 340 ms 45764 KB Output is correct
13 Correct 358 ms 46028 KB Output is correct
14 Correct 373 ms 50448 KB Output is correct
15 Correct 340 ms 53604 KB Output is correct
16 Correct 368 ms 48052 KB Output is correct
17 Correct 404 ms 49624 KB Output is correct
18 Correct 416 ms 47276 KB Output is correct
19 Correct 392 ms 46940 KB Output is correct
20 Correct 719 ms 67644 KB Output is correct
21 Correct 577 ms 62916 KB Output is correct
22 Correct 585 ms 64580 KB Output is correct
23 Correct 606 ms 62812 KB Output is correct
24 Correct 850 ms 72112 KB Output is correct
25 Correct 724 ms 75076 KB Output is correct
26 Correct 642 ms 71808 KB Output is correct
27 Correct 743 ms 71356 KB Output is correct
28 Correct 759 ms 64100 KB Output is correct
29 Correct 681 ms 64716 KB Output is correct
30 Correct 574 ms 61572 KB Output is correct
31 Correct 614 ms 62652 KB Output is correct
32 Correct 721 ms 64120 KB Output is correct
33 Correct 698 ms 64396 KB Output is correct
34 Correct 704 ms 64596 KB Output is correct
35 Correct 662 ms 61040 KB Output is correct