#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 ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
# |
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 |
# |
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 |
# |
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 |
# |
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 |