oj.uz

답안 #702499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702499 2023-02-24T08:10:55 Z Chal1shkan Sjekira (COCI20_sjekira) C++14
40 / 110
 52 ms 9036 KB 
# include <bits/stdc++.h>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll maxn = 1e5 + 25;
const ll inf = 1e18 + 0;
const ll mod = 998244353;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;

ll n, a[maxn];
vector <ll> g[maxn];
ll ord[maxn];
ll q[maxn];

bool cmp (ll x, ll y)
{
	return (a[x] < a[y]);
}

struct DSU
{
	ll par[maxn];
	DSU ()
	{
		iota(par, par + maxn, 0);	
	}	
	ll find_set (ll v)
	{
		if (v == par[v]) return v;
		return v = find_set(par[v]);
	}
	void unite (ll u, ll v)
	{
		u = find_set(u);
		v = find_set(v);
		if (u != v)
		{
			par[v] = u;
			a[u] = max(a[u], a[v]);
		}
	}
} dsu;

void ma1n (/* SABR */)
{
	cin >> n;
	for (ll i = 1; i <= n; ++i)
	{
		cin >> a[i];
		q[i] = a[i];
		ord[i] = i;
	}
	for (ll i = 1; i < n; ++i)
	{
		ll u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	sort(ord + 1, ord + 1 + n, cmp);
	ll ans = 0;
	for (ll i = 1; i <= n; ++i)
	{
		ll v = ord[i];
		for (ll to : g[v])
		{
			if (a[v] > a[to])
			{
				v = dsu.find_set(v);
				to = dsu.find_set(to);
				if (v != to)
				{
					ans += a[v] + a[to];
					dsu.unite(v, to);
				}
			}
		}
	}
	cout << ans;
}       

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("angry.in", "r", stdin);
//    freopen("angry.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 7848 KB Output is correct
2 Correct 33 ms 6764 KB Output is correct
3 Correct 31 ms 6612 KB Output is correct
4 Correct 35 ms 7124 KB Output is correct
5 Correct 52 ms 8804 KB Output is correct
6 Incorrect 40 ms 9036 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 42 ms 7848 KB Output is correct
7 Correct 33 ms 6764 KB Output is correct
8 Correct 31 ms 6612 KB Output is correct
9 Correct 35 ms 7124 KB Output is correct
10 Correct 52 ms 8804 KB Output is correct
11 Incorrect 40 ms 9036 KB Output isn't correct
12 Halted 0 ms 0 KB -