Submission #872197

#	Time	Username	Problem	Language	Result	Execution time	Memory
872197		Onur_Ilgaz	Sjekira (COCI20_sjekira)	C++17	110 / 110	41 ms	11356 KiB

sjekira

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 100000
using namespace std;
int par[N], mx[N];
vector <vector<int> > adj;
vector <pair<int, int> > arr;
vector <int> val;
int ans = 0;

int parent(int x) {
	if(par[x] == x) return x;
	par[x] = parent(par[x]);
	mx[x] = max(mx[x], mx[par[x]]);
	return par[x];
}

void merge(int x, int y) {
	x = parent(x);
	y = parent(y);
	par[y] = x;
	ans += mx[y] + mx[x];
	mx[x] = max(mx[x], mx[y]);
}

int32_t main(){
	fast
	int n;
	cin >> n;
	arr.resize(n);
	adj.resize(n);
	val.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> val[i];
		arr[i].first = val[i];
		arr[i].second = i;
	}
	sort(arr.begin(), arr.end());
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		if(val[a] > val[b] or (val[a] == val[b] and a > b)) {
			// önce a çıkartılacak
			adj[a].push_back(b);
		}
		else {
			adj[b].push_back(a);
		}
	}
	// pre-calc for dsu
	for(int i = 0; i < n; i++) par[i] = i, mx[i] = val[i];
	// now do the merging
	for(int i = 0; i < n; i++) {
		int node = arr[i].second;
		for(auto it:adj[node]) {
			merge(node, it);
			// cout << node << " " << it << " " << ans << "\n";
		}
	}
	cout << ans << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60