oj.uz

Submission #578420

# Submission time Handle Problem Language Result Execution time Memory
578420 2022-06-16T18:26:07 Z AlperenT Min-max tree (BOI18_minmaxtree) C++17
0 / 100
 208 ms 37836 KB 
#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(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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13440 KB Output is correct
2 Correct 7 ms 13480 KB Output is correct
3 Incorrect 7 ms 13396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13440 KB Output is correct
2 Correct 7 ms 13480 KB Output is correct
3 Incorrect 7 ms 13396 KB Output isn't correct
4 Halted 0 ms 0 KB -