oj.uz

Submission #445481

# Submission time Handle Problem Language Result Execution time Memory
445481 2021-07-18T08:49:16 Z grt Sjekira (COCI20_sjekira) C++17
40 / 110
 66 ms 9816 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 100 * 1000 + 10;
int n;
pi val[nax];
int par[nax], siz[nax], mx[nax];
vi V[nax];

int Fund(int x) {
	if(par[x] != x) par[x] = Fund(par[x]);
	return par[x];
}

void Onion(int a, int b) {
	a = Fund(a); b = Fund(b);
	if(a == b) return;
	if(siz[a] < siz[b]) swap(a, b);
	siz[a] += siz[b];
	mx[a] = max(mx[a], mx[b]);
	par[b] = a;
}

ll ans;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		par[i] = i;
		siz[i] = 1;
		cin >> mx[i];
		val[i] = {mx[i], i};
	}
	for(int a,b,i = 1; i < n; ++i) {
		cin >> a >> b;
		V[a].PB(b);
		V[b].PB(a);
	}
	sort(val + 1, val + n + 1);
	for(int i = 1; i <= n; ++i) {
		int u = val[i].ND;
		for(auto nbh : V[u]) {
			if(mx[Fund(nbh)] <= val[i].ST) {
				ans += val[i].ST;
				ans += mx[Fund(nbh)];
				Onion(nbh, u);
			}
		}
	}
	cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8504 KB Output is correct
2 Correct 38 ms 6996 KB Output is correct
3 Correct 39 ms 7056 KB Output is correct
4 Correct 41 ms 7344 KB Output is correct
5 Correct 66 ms 9816 KB Output is correct
6 Incorrect 49 ms 9752 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2684 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct
6 Correct 60 ms 8504 KB Output is correct
7 Correct 38 ms 6996 KB Output is correct
8 Correct 39 ms 7056 KB Output is correct
9 Correct 41 ms 7344 KB Output is correct
10 Correct 66 ms 9816 KB Output is correct
11 Incorrect 49 ms 9752 KB Output isn't correct
12 Halted 0 ms 0 KB -