제출 #578424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578424		AlperenT	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	292 ms	45744 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

const int N = 7e4 + 5;

int n, k, a, b, z, ans[N], cnt[N], color[N];

char c;

vector<int> mn[N], mx[N], cycle, nodes;

map<int, int> mnmp[N], mxmp[N], cmprs, revcmprs;

vector<pair<int, int>> tree[N], graph[N];

pair<int, int> edges[N], edgerange[N], par[N];

struct Path{
	char c;
	int a, b, z;
};

Path paths[N];

void dfs(int v, int p){
	cnt[v] = 1;
	int maxn = -1;

	for(auto e : tree[v]){
		if(e.first != p){
			dfs(e.first, v);

			cnt[v] += cnt[e.first];

			if(maxn == -1 || cnt[e.first] > cnt[maxn]) maxn = e.first;

			a = b = -1;

			if(!mnmp[e.first].empty() && !mxmp[e.first].empty()){
				a = (*prev(mnmp[e.first].end())).first, b = (*mxmp[e.first].begin()).first;

				graph[a].push_back({b, e.second});
				graph[b].push_back({a, e.second});

				edgerange[e.second] = {a, b};
			}
			else if(!mnmp[e.first].empty() && mxmp[e.first].empty()){
				a = b = (*prev(mnmp[e.first].end())).first;

				graph[a].push_back({b, e.second});
				graph[b].push_back({a, e.second});

				edgerange[e.second] = {a, b};
			}
			else if(mnmp[e.first].empty() && !mxmp[e.first].empty()){
				a = b = (*mxmp[e.first].begin()).first;

				graph[a].push_back({b, e.second});
				graph[b].push_back({a, e.second});

				edgerange[e.second] = {a, b};
			}
			else edgerange[e.second] = {1, 1};

			if(a != -1) a = revcmprs[a];
			if(b != -1) b = revcmprs[b];

			// cout << v << " " << e.first << " " << e.second << " " << a << " " << b << "\n";
		}
	}

	if(maxn != -1) swap(mnmp[v], mnmp[maxn]), swap(mxmp[v], mxmp[maxn]);

	for(auto x : mn[v]) if(++mnmp[v][x] == 2) mnmp[v].erase(x);
	for(auto x : mx[v]) if(++mxmp[v][x] == 2) mxmp[v].erase(x);

	for(auto e : tree[v]){
		if(e.first != p && e.first != maxn){
			for(auto x : mnmp[e.first]) if((mnmp[v][x.first] += x.second) == 2) mnmp[v].erase(x.first);
			for(auto x : mxmp[e.first]) if((mxmp[v][x.first] += x.second) == 2) mxmp[v].erase(x.first);
		}
	}
}

void dfs2(int v, int p){
	color[v] = 1;

	nodes.push_back(v);

	for(auto e : graph[v]){
		if(e.second != p){
			if(color[e.first] == 0) par[e.first] = {v, e.second}, dfs2(e.first, e.second);
			else if(color[e.first] == 1 && cycle.empty()){
				int vv = v;

				while(vv != e.first){
					ans[par[vv].second] = vv;

					cycle.push_back(vv);

					vv = par[vv].first;
				}

				ans[e.second] = e.first;

				cycle.push_back(e.first);
			}
		}
	}

	color[v] = 2;
}

void dfs3(int v){
	color[v] = 2;

	for(auto e : graph[v]){
		if(color[e.first] == 0){
			ans[e.second] = e.first;
			dfs3(e.first);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	cin >> n;

	for(int i = 1; i <= n - 1; i++){
		cin >> edges[i].first >> edges[i].second;

		tree[edges[i].first].push_back({edges[i].second, i});
		tree[edges[i].second].push_back({edges[i].first, i});
	}

	cin >> k;

	for(int i = 1; i <= k; i++){
		cin >> c >> a >> b >> z;

		paths[i] = {c, a, b, z};

		cmprs[z] = 1;
	}

	int cur = 0;

	for(auto &p : cmprs){
		p.second = ++cur;

		revcmprs[cur] = p.first;
	}

	for(int i = 1; i <= k; i++){
		paths[i].z = cmprs[paths[i].z];

		if(paths[i].c == 'M') mx[paths[i].a].push_back(paths[i].z), mx[paths[i].b].push_back(paths[i].z);
		else if(paths[i].c == 'm') mn[paths[i].a].push_back(paths[i].z), mn[paths[i].b].push_back(paths[i].z);
	}

	dfs(1, 0);

	for(int i = 1; i <= n; i++){
		if(!color[i] && !graph[i].empty()){
			cycle.clear(), nodes.clear();

			dfs2(i, 0);

			for(auto x : nodes) color[x] = 0;

			for(auto x : cycle) color[x] = 2;

			for(auto x : cycle){
				dfs3(x);
			}
		}
	}

	for(int i = 1; i <= n - 1; i++){
		if(ans[i] == 0) ans[i] = edgerange[i].first;
	}

	for(int i = 1; i <= n - 1; i++) ans[i] = revcmprs[ans[i]];

	for(int i = 1; i <= n - 1; i++) cout << edges[i].first << " " << edges[i].second << " " << ans[i] << "\n";
}

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42