oj.uz

Submission #474080

# Submission time Handle Problem Language Result Execution time Memory
474080 2021-09-16T19:44:20 Z CaroLinda Sjekira (COCI20_sjekira) C++14
20 / 110
 283 ms 22448 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() && (it->second != find(it->second) || find(it->second) == p.second ) )
			it = s[p.second].erase(it) ;
			
		if(it == s[p.second].end()) return 0 ;
			
		tot += p.first + t[it->second] ;
		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 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4996 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 18760 KB Output is correct
2 Correct 137 ms 15480 KB Output is correct
3 Correct 127 ms 15020 KB Output is correct
4 Correct 149 ms 16416 KB Output is correct
5 Correct 283 ms 21964 KB Output is correct
6 Correct 121 ms 22448 KB Output is correct
7 Correct 103 ms 19912 KB Output is correct
8 Correct 93 ms 18600 KB Output is correct
9 Correct 61 ms 13976 KB Output is correct
10 Correct 145 ms 22380 KB Output is correct

Subtask #3
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 5000 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4996 KB Output is correct
6 Incorrect 4 ms 5068 KB Output isn't correct
7 Halted 0 ms 0 KB -

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 5000 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4996 KB Output is correct
6 Correct 184 ms 18760 KB Output is correct
7 Correct 137 ms 15480 KB Output is correct
8 Correct 127 ms 15020 KB Output is correct
9 Correct 149 ms 16416 KB Output is correct
10 Correct 283 ms 21964 KB Output is correct
11 Correct 121 ms 22448 KB Output is correct
12 Correct 103 ms 19912 KB Output is correct
13 Correct 93 ms 18600 KB Output is correct
14 Correct 61 ms 13976 KB Output is correct
15 Correct 145 ms 22380 KB Output is correct
16 Incorrect 4 ms 5068 KB Output isn't correct
17 Halted 0 ms 0 KB -