Submission #931349

#	Time	Username	Problem	Language	Result	Execution time	Memory
931349		Whisper	Sjekira (COCI20_sjekira)	C++17	110 / 110	34 ms	9860 KiB

sjekira

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

using namespace std; 
using ll = long long;
using str = string;

#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for ( int i = b ; i >= a ; i-- )
#define all(x) x.begin() , x.end()
#define ii pair<ll , int>
#define fi first
#define se second
#define debug(x) cerr << x << " ";

constexpr ll LINF = ( 1e18 + 5 );
constexpr int INF = ( 1e9 + 5 );
constexpr ll MAX = 1e6 + 5;
constexpr int MOD = 1e9;

void setupIO( const string& PROB ){
	cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
//	freopen( (PROB + ".inp").c_str(), "r", stdin);
//	freopen( (PROB + ".out").c_str(), "w", stdout);
}
bool vst[MAX];
ll cost[MAX];
struct DSU{
	ll n, ans;
	vector<ll> par, sz, mx;
	DSU( int n ): par(n + 1) , sz(n + 1), mx(n + 1){
		this->n = n; ans = 0;
	}
	void make_set(){
		for ( int i = 1 ; i <= n ; i++ ) par[i] = i, sz[i] = 1, mx[i] = cost[i];
	}
	ll Find( int u ){
		if ( u == par[u] ) return u;
		return par[u] = Find(par[u]);
	}
	bool Union( int a, int b ){
		a = Find(a);
		b = Find(b);
		if ( a == b ) return false;
		if ( sz[a] < sz[b] ) swap( a, b );
		ans += mx[a] + mx[b];
		mx[a] = max( mx[a] , mx[b] );
		sz[a] += sz[b];
		par[b] = a;
		sz[b] = 0;
		return true;
	}
};

struct Node{
	ll u, v, w;
	bool operator < ( const Node& Other ) const{
		return w < Other.w;
	}
};

void Whisper(){
	int n; cin >> n;
	vector<Node> Edge;
	for ( int i = 1 ; i <= n ; i++ ) cin >> cost[i];
	for ( int i = 1 ; i < n ; i++ ){
		Node e;
		cin >> e.v >> e.u;
		e.w = max( cost[e.v], cost[e.u] );
		Edge.push_back(e);
	}
	sort( Edge.begin() , Edge.end() );
	DSU dsu(n);
	dsu.make_set();
	for ( auto&[u, v, w] : Edge ){
		//cout << u << " " << v << " " << w << '\n';
		dsu.Union(u , v);
	}
	cout << dsu.ans;
}	

signed main(){
	setupIO("__Whisper");
    ll Test = 1; //cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        //
        cout << '\n';
    }
}

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