oj.uz

답안 #574568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574568 2022-06-08T20:39:09 Z FatihSolak Min-max tree (BOI18_minmaxtree) C++17
29 / 100
 695 ms 96360 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)}] = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 42608 KB Output is correct
2 Correct 19 ms 42596 KB Output is correct
3 Correct 19 ms 42516 KB Output is correct
4 Correct 23 ms 42608 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 695 ms 95028 KB Output is correct
2 Correct 613 ms 92052 KB Output is correct
3 Correct 633 ms 88232 KB Output is correct
4 Correct 628 ms 96360 KB Output is correct
5 Correct 587 ms 90044 KB Output is correct
6 Correct 639 ms 89368 KB Output is correct
7 Correct 584 ms 84028 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 371 ms 70764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 42608 KB Output is correct
2 Correct 19 ms 42596 KB Output is correct
3 Correct 19 ms 42516 KB Output is correct
4 Correct 23 ms 42608 KB Output is correct
5 Correct 695 ms 95028 KB Output is correct
6 Correct 613 ms 92052 KB Output is correct
7 Correct 633 ms 88232 KB Output is correct
8 Correct 628 ms 96360 KB Output is correct
9 Correct 587 ms 90044 KB Output is correct
10 Correct 639 ms 89368 KB Output is correct
11 Correct 584 ms 84028 KB Output is correct
12 Incorrect 371 ms 70764 KB Output isn't correct
13 Halted 0 ms 0 KB -