oj.uz

Submission #574567

# Submission time Handle Problem Language Result Execution time Memory
574567 2022-06-08T20:38:19 Z FatihSolak Min-max tree (BOI18_minmaxtree) C++17
29 / 100
 611 ms 96464 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)}] = {-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:needed){
		assert(u.second == 0);
	}
	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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42560 KB Output is correct
2 Correct 20 ms 42572 KB Output is correct
3 Correct 22 ms 42592 KB Output is correct
4 Correct 20 ms 42572 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 95168 KB Output is correct
2 Correct 594 ms 92220 KB Output is correct
3 Correct 574 ms 88396 KB Output is correct
4 Correct 611 ms 96464 KB Output is correct
5 Correct 610 ms 90264 KB Output is correct
6 Correct 605 ms 89320 KB Output is correct
7 Correct 577 ms 84196 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 70648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42560 KB Output is correct
2 Correct 20 ms 42572 KB Output is correct
3 Correct 22 ms 42592 KB Output is correct
4 Correct 20 ms 42572 KB Output is correct
5 Correct 610 ms 95168 KB Output is correct
6 Correct 594 ms 92220 KB Output is correct
7 Correct 574 ms 88396 KB Output is correct
8 Correct 611 ms 96464 KB Output is correct
9 Correct 610 ms 90264 KB Output is correct
10 Correct 605 ms 89320 KB Output is correct
11 Correct 577 ms 84196 KB Output is correct
12 Incorrect 368 ms 70648 KB Output isn't correct
13 Halted 0 ms 0 KB -