Submission #474081

#	Time	Username	Problem	Language	Result	Execution time	Memory
474081		CaroLinda	Sjekira (COCI20_sjekira)	C++14	110 / 110	330 ms	21936 KiB

sjekira

#include <bits/stdc++.h>
 
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
 
const int MAXN = 1e5+10 ;
 
using namespace std ;
 
int N ;
int dsu[MAXN] , t[MAXN] ;
set<pair<int,int>> mySet ;
set< pair<int,int> > s[MAXN] ;
 
int find(int x) { return dsu[x] = ( x == dsu[x] ) ? x : find(dsu[x]) ; }
void join(int x, int y)
{
	x = find(x) ;
	y = find(y) ;
	
	if(x == y) return ;
	
	if( sz(s[x]) > sz(s[y]) ) swap(x,y) ;
	for(auto e : s[x]) 
		if( find(e.second) != y && find(e.second) != x )
			s[y].insert(e) ;
	
	mySet.erase( make_pair(t[x] , x) ) ;
	mySet.erase( make_pair(t[y] , y) ) ;
	
	s[x].clear() ;
	dsu[x] = y ;
	t[y] = max(t[y] , t[x]) ;
	
	mySet.insert( make_pair(t[y] , y) ) ;
	
}
 
int main()
{
	scanf("%d", &N ) ;
	for(int i = 1 ; i <= N ; i++ ) 
	{
		dsu[i] = i ;
		scanf("%d", &t[i]) ;
		mySet.insert(make_pair(t[i] , i)) ;
	}
	for(int i = 0 ,a , b ; i < N-1 ; i++ )
	{
		scanf("%d %d", &a, &b ) ;
		s[a].insert(make_pair(t[b] , b)) ;
		s[b].insert(make_pair(t[a] , a)) ;
	}
	
	long long tot = 0 ;
	
	while(sz(mySet) > 1 )
	{
		pair<int,int> p = *mySet.begin() ;
				
		auto it = s[p.second].begin() ;
		while( it != s[p.second].end() && find(it->second) == p.second  )
			it = s[p.second].erase(it) ;
			
		if(it == s[p.second].end()) return 0 ;
		
		int k = it->second ;
		k = find(k) ;
			
		tot += p.first + t[k] ;
		join(p.second, it->second ) ;
		
	}
	
	printf("%lld\n" , tot ) ; 
}

Compilation message (stderr)

sjekira.cpp: In function 'int main()':
sjekira.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
sjekira.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d", &t[i]) ;
      |   ~~~~~^~~~~~~~~~~~~
sjekira.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d %d", &a, &b ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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