oj.uz

Submission #574573

# Submission time Handle Problem Language Result Execution time Memory
574573 2022-06-08T20:49:21 Z FatihSolak Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 936 ms 104852 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;
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)}] = {-2e9,2e9};
		ans[{min(u,v),max(u,v)}] = 2e9;
	}
	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});
		}

	}
	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:125: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]
  125 |  assert(ans.size() == n-1);
      |         ~~~~~~~~~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42580 KB Output is correct
2 Correct 20 ms 42580 KB Output is correct
3 Correct 20 ms 42524 KB Output is correct
4 Correct 19 ms 42580 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 95092 KB Output is correct
2 Correct 625 ms 92076 KB Output is correct
3 Correct 587 ms 88516 KB Output is correct
4 Correct 649 ms 96416 KB Output is correct
5 Correct 611 ms 90184 KB Output is correct
6 Correct 637 ms 89240 KB Output is correct
7 Correct 624 ms 84040 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 71092 KB Output is correct
2 Correct 387 ms 72848 KB Output is correct
3 Correct 395 ms 76768 KB Output is correct
4 Correct 365 ms 80064 KB Output is correct
5 Correct 406 ms 75064 KB Output is correct
6 Correct 440 ms 76744 KB Output is correct
7 Correct 430 ms 74548 KB Output is correct
8 Correct 406 ms 73984 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42580 KB Output is correct
2 Correct 20 ms 42580 KB Output is correct
3 Correct 20 ms 42524 KB Output is correct
4 Correct 19 ms 42580 KB Output is correct
5 Correct 634 ms 95092 KB Output is correct
6 Correct 625 ms 92076 KB Output is correct
7 Correct 587 ms 88516 KB Output is correct
8 Correct 649 ms 96416 KB Output is correct
9 Correct 611 ms 90184 KB Output is correct
10 Correct 637 ms 89240 KB Output is correct
11 Correct 624 ms 84040 KB Output is correct
12 Correct 421 ms 71092 KB Output is correct
13 Correct 387 ms 72848 KB Output is correct
14 Correct 395 ms 76768 KB Output is correct
15 Correct 365 ms 80064 KB Output is correct
16 Correct 406 ms 75064 KB Output is correct
17 Correct 440 ms 76744 KB Output is correct
18 Correct 430 ms 74548 KB Output is correct
19 Correct 406 ms 73984 KB Output is correct
20 Correct 820 ms 97528 KB Output is correct
21 Correct 634 ms 91912 KB Output is correct
22 Correct 660 ms 93416 KB Output is correct
23 Correct 714 ms 91792 KB Output is correct
24 Correct 936 ms 101648 KB Output is correct
25 Correct 795 ms 104852 KB Output is correct
26 Correct 733 ms 101412 KB Output is correct
27 Correct 808 ms 101048 KB Output is correct
28 Correct 849 ms 94232 KB Output is correct
29 Correct 746 ms 94820 KB Output is correct
30 Correct 663 ms 90672 KB Output is correct
31 Correct 713 ms 91920 KB Output is correct
32 Correct 870 ms 94200 KB Output is correct
33 Correct 831 ms 93916 KB Output is correct
34 Correct 797 ms 94048 KB Output is correct
35 Correct 762 ms 90332 KB Output is correct