oj.uz

Submission #474081

# Submission time Handle Problem Language Result Execution time Memory
474081 2021-09-16T19:46:42 Z CaroLinda Sjekira (COCI20_sjekira) C++14
110 / 110
 330 ms 21936 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 4940 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 16944 KB Output is correct
2 Correct 137 ms 14172 KB Output is correct
3 Correct 124 ms 13956 KB Output is correct
4 Correct 143 ms 14908 KB Output is correct
5 Correct 275 ms 19840 KB Output is correct
6 Correct 122 ms 20452 KB Output is correct
7 Correct 104 ms 18136 KB Output is correct
8 Correct 92 ms 17036 KB Output is correct
9 Correct 68 ms 12812 KB Output is correct
10 Correct 117 ms 20284 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 4940 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5112 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 4940 KB Output is correct
6 Correct 189 ms 16944 KB Output is correct
7 Correct 137 ms 14172 KB Output is correct
8 Correct 124 ms 13956 KB Output is correct
9 Correct 143 ms 14908 KB Output is correct
10 Correct 275 ms 19840 KB Output is correct
11 Correct 122 ms 20452 KB Output is correct
12 Correct 104 ms 18136 KB Output is correct
13 Correct 92 ms 17036 KB Output is correct
14 Correct 68 ms 12812 KB Output is correct
15 Correct 117 ms 20284 KB Output is correct
16 Correct 5 ms 5068 KB Output is correct
17 Correct 5 ms 5068 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 4 ms 5112 KB Output is correct
20 Correct 5 ms 5068 KB Output is correct
21 Correct 43 ms 8908 KB Output is correct
22 Correct 38 ms 8268 KB Output is correct
23 Correct 298 ms 21104 KB Output is correct
24 Correct 201 ms 16532 KB Output is correct
25 Correct 189 ms 16324 KB Output is correct
26 Correct 127 ms 12556 KB Output is correct
27 Correct 131 ms 13932 KB Output is correct
28 Correct 259 ms 16888 KB Output is correct
29 Correct 114 ms 13084 KB Output is correct
30 Correct 330 ms 21936 KB Output is correct