oj.uz

Submission #374465

# Submission time Handle Problem Language Result Execution time Memory
374465 2021-03-07T10:08:41 Z Araragi Sjekira (COCI20_sjekira) C++14
0 / 110
 101 ms 2148 KB 
/*
* 	author: Araragi
*/

// 3

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define F first
#define S second
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int cost[100001];

vector<int> dsu;
int ans;

inline int get(int x)
{
	return (dsu[x] == x ? x : dsu[x] = get(dsu[x]));
}

inline bool unite(int x, int y)
{
	int xx = get(x);
	int yy = get(y);

	if (xx != yy)
	{
		dsu[xx] = yy;

		ans += cost[xx];
        ans += cost[yy];

        cost[yy] = max(cost[yy], cost[xx]);

		return true;
	}

	return false;
}

bool cmp(pair<int, int> x, pair<int, int> y)
{
	return max(cost[x.F], cost[x.S]) < max(cost[y.F], cost[y.S]);
}

int main()
{
	//ifstream cin("vacation.in");
	//ofstream cout("vacation.out");

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> cost[i];

	dsu.resize(n + 1);
	iota(dsu.begin(), dsu.end(), 0);

   	vector<pair<int, int> > edges;

   	for (int i = 1; i < n; i++)
   	{
   		int x, y;
   		cin >> x >> y;
   		edges.pb({x, y});
   	}

   	sort(edges.begin(), edges.end(), cmp);

   	for (auto edge : edges)
   		if (unite(edge.F, edge.S))
   		{
   		    // without code, need void
   		}

   	cout << ans;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 60.0

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