oj.uz

Submission #473708

# Submission time Handle Problem Language Result Execution time Memory
473708 2021-09-15T21:09:34 Z CaroLinda Sjekira (COCI20_sjekira) C++14
20 / 110
 1000 ms 22444 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->second != find(it->second) || find(it->second) == p.second )
			it = s[p.second].erase(it) ;
			
		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 4996 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 4940 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 18792 KB Output is correct
2 Correct 132 ms 15440 KB Output is correct
3 Correct 123 ms 15080 KB Output is correct
4 Correct 143 ms 16312 KB Output is correct
5 Correct 240 ms 21896 KB Output is correct
6 Correct 115 ms 22444 KB Output is correct
7 Correct 100 ms 19908 KB Output is correct
8 Correct 91 ms 18700 KB Output is correct
9 Correct 62 ms 13944 KB Output is correct
10 Correct 117 ms 22356 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 4996 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 4940 KB Output is correct
6 Execution timed out 1091 ms 5140 KB Time limit exceeded
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 4996 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 4940 KB Output is correct
6 Correct 203 ms 18792 KB Output is correct
7 Correct 132 ms 15440 KB Output is correct
8 Correct 123 ms 15080 KB Output is correct
9 Correct 143 ms 16312 KB Output is correct
10 Correct 240 ms 21896 KB Output is correct
11 Correct 115 ms 22444 KB Output is correct
12 Correct 100 ms 19908 KB Output is correct
13 Correct 91 ms 18700 KB Output is correct
14 Correct 62 ms 13944 KB Output is correct
15 Correct 117 ms 22356 KB Output is correct
16 Execution timed out 1091 ms 5140 KB Time limit exceeded
17 Halted 0 ms 0 KB -