Submission #419417

#	Time	Username	Problem	Language	Result	Execution time	Memory
419417		NurstanDuisengaliev	Sjekira (COCI20_sjekira)	C++14	40 / 110	1063 ms	16112 KiB

sjekira

// Nurstan Duisengaliev(REALBOY)
// Respa Gold_2022
// IZHO GOLD_2022
// IOI_2022 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3")*/                   
      
#include <bits/stdc++.h>
 
#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define mp make_pair
#define F first
#define S second
#define ppf pop_front
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <int, int>
#define pll pair <ll, ll>
#define boost() ios_base::sync_with_stdio(0), cin.tie(0)
#define sz(x) (int)x.size()
 
using namespace std;
 
const int N = (int)2e5 + 123;
const int mod = (int)1e9 + 7;
const ll INF = (ll)1e18 + 1;
int n;
vector <pii> g[N];
bool used[N];
vector <pii> order; 
int a[N];
int maxi = 0;
void Dfs (int v, int p) {
	maxi = max (maxi, a[v]);
	for (auto to : g[v]) {
		if (to.F != p && !used[to.S]) {
			Dfs (to.F, v);	
		}
	}
}
void solve () {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		order.pb (mp (a[i], i));
	}
	sort (all (order));
	reverse (all (order));
	for (int i = 1; i < n; i ++) {
		int l, r;
		cin >> l >> r;
		g[l].pb (mp (r, i));
		g[r].pb (mp (l, i));
	}
	ll sum = 0;	
	for (auto it : order) {
		int v = it.S;
		for (auto to : g[v]) {
			if (!used[to.S]) {
				used[to.S] = 1;
				maxi = 0;
				Dfs (to.F, v);
				sum += maxi + a[v];	
			}
		}
	}
	cout << sum;
}   	
 
main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	boost ();
	int TT = 1;
//    cin >> TT;
	while (TT --) {
		solve ();
	}
	return 0;	                                    
}

Compilation message (stderr)

sjekira.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main () {
      | ^~~~

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