oj.uz

Submission #574566

# Submission time Handle Problem Language Result Execution time Memory
574566 2022-06-08T20:31:02 Z FatihSolak Min-max tree (BOI18_minmaxtree) C++17
29 / 100
 631 ms 98792 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: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 19 ms 42580 KB Output is correct
2 Correct 19 ms 42576 KB Output is correct
3 Correct 19 ms 42580 KB Output is correct
4 Correct 21 ms 42608 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 96520 KB Output is correct
2 Correct 629 ms 94440 KB Output is correct
3 Correct 607 ms 90428 KB Output is correct
4 Correct 603 ms 98792 KB Output is correct
5 Correct 585 ms 92372 KB Output is correct
6 Correct 631 ms 91600 KB Output is correct
7 Correct 614 ms 86376 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 42580 KB Output is correct
2 Correct 19 ms 42576 KB Output is correct
3 Correct 19 ms 42580 KB Output is correct
4 Correct 21 ms 42608 KB Output is correct
5 Correct 631 ms 96520 KB Output is correct
6 Correct 629 ms 94440 KB Output is correct
7 Correct 607 ms 90428 KB Output is correct
8 Correct 603 ms 98792 KB Output is correct
9 Correct 585 ms 92372 KB Output is correct
10 Correct 631 ms 91600 KB Output is correct
11 Correct 614 ms 86376 KB Output is correct
12 Incorrect 349 ms 70964 KB Output isn't correct
13 Halted 0 ms 0 KB -