oj.uz

Submission #419417

# Submission time Handle Problem Language Result Execution time Memory
419417 2021-06-07T05:33:32 Z NurstanDuisengaliev Sjekira (COCI20_sjekira) C++14
40 / 110
 1000 ms 16112 KB 
// 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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13204 KB Output is correct
2 Correct 53 ms 10864 KB Output is correct
3 Correct 48 ms 10488 KB Output is correct
4 Correct 55 ms 12168 KB Output is correct
5 Correct 82 ms 14096 KB Output is correct
6 Execution timed out 1063 ms 16112 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 4 ms 5080 KB Output is correct
8 Correct 4 ms 5000 KB Output is correct
9 Correct 6 ms 5068 KB Output is correct
10 Correct 6 ms 5068 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 66 ms 13204 KB Output is correct
7 Correct 53 ms 10864 KB Output is correct
8 Correct 48 ms 10488 KB Output is correct
9 Correct 55 ms 12168 KB Output is correct
10 Correct 82 ms 14096 KB Output is correct
11 Execution timed out 1063 ms 16112 KB Time limit exceeded
12 Halted 0 ms 0 KB -