oj.uz

Submission #876101

# Submission time Handle Problem Language Result Execution time Memory
876101 2023-11-21T08:55:29 Z Danet Sjekira (COCI20_sjekira) C++14
110 / 110
 85 ms 7708 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")

#define tof_io  ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define double  long double
#define int     long long
#define pb      push_back

#define all(x)  x.begin(),x.end()
#define endl    '\n'
#define sz(x) 	x.size()
const int mod = 1e9 + 7; //998244353 1e9+7 1e9+9
const int N = 1e6 + 1;	
const int lg = 23;

const int inf = 1e18;
int fac[N];
int inv[N];
int cnt[N];
int n ;
vector<int> vc;
vector<pair<int, int> > adj;
int ans = 0;
int  dnt_pow	(int a, int b, int md = mod){int ans = 1; while(b){if(b&1){ans = (a*ans)%md;}a = (a*a)%md;b >>= 1;}return ans ;}
void dnt_bld	(){fac[0] = 1; inv[0] = dnt_pow(fac[0],mod-2) ;for(int i = 1 ; i < N ; i++) {fac[i] = (fac[i-1] * i) % mod;inv[i] = dnt_pow( fac[i] , mod-2);}}
int  dnt_ncr	(int r,int n){if(r>n) return 0; return fac[n] * inv[r] % mod * inv[n-r] % mod;}
bool cmp		(pair<int, int> x, pair<int, int> y){return max(cnt[x.first], cnt[x.second]) < max(cnt[y.first], cnt[y.second]);}

int get(int x){return (vc[x] == x ? x : vc[x] = get(vc[x]));}
void merg(int x, int y)
{
	int a = get(x);
	int b = get(y);
	if (a != b)
	{
		vc[a] = b;
		ans = ans + cnt[a];
        ans = ans + cnt[b];
        cnt[b] = max(cnt[b], cnt[a]);
	}

}
int32_t main()
{
	cin >> n;
	vc.pb(0);
	for (int i = 1; i <= n; i++)
	{
		cin >> cnt[i];
		vc.pb(i);
	}
   	for (int i = 1; i < n; i++)
   	{
   		int x, y;
   		cin >> x >> y;
   		adj.pb(make_pair(x,y));
   	}
   	sort(all(adj), cmp);
 
   	for (auto v : adj)
		merg(v.first, v.second);
 
   	cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6980 KB Output is correct
2 Correct 47 ms 5460 KB Output is correct
3 Correct 45 ms 5448 KB Output is correct
4 Correct 53 ms 6728 KB Output is correct
5 Correct 85 ms 7392 KB Output is correct
6 Correct 81 ms 7708 KB Output is correct
7 Correct 68 ms 7236 KB Output is correct
8 Correct 66 ms 6984 KB Output is correct
9 Correct 48 ms 5216 KB Output is correct
10 Correct 76 ms 7492 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 63 ms 6980 KB Output is correct
7 Correct 47 ms 5460 KB Output is correct
8 Correct 45 ms 5448 KB Output is correct
9 Correct 53 ms 6728 KB Output is correct
10 Correct 85 ms 7392 KB Output is correct
11 Correct 81 ms 7708 KB Output is correct
12 Correct 68 ms 7236 KB Output is correct
13 Correct 66 ms 6984 KB Output is correct
14 Correct 48 ms 5216 KB Output is correct
15 Correct 76 ms 7492 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 18 ms 3932 KB Output is correct
22 Correct 15 ms 1776 KB Output is correct
23 Correct 77 ms 7240 KB Output is correct
24 Correct 54 ms 6660 KB Output is correct
25 Correct 54 ms 6724 KB Output is correct
26 Correct 35 ms 4932 KB Output is correct
27 Correct 41 ms 5208 KB Output is correct
28 Correct 49 ms 6332 KB Output is correct
29 Correct 33 ms 4940 KB Output is correct
30 Correct 80 ms 7636 KB Output is correct