oj.uz

답안 #364761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364761 2021-02-10T00:02:35 Z MohamedAhmed04 Sjekira (COCI20_sjekira) C++14
40 / 110
 1000 ms 22376 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n ;

vector< set<int> >adj(MAX) ;

vector< pair<int , int> >vp ;

int dfs(int node , int par)
{
	int x = arr[node] ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		x = max(x , dfs(child , node)) ;
	}
	return x ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
	{
		cin>>arr[i] ;
		vp.emplace_back(arr[i] , i) ;
	}
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].insert(y) ;
		adj[y].insert(x) ;
	}
	sort(vp.begin() , vp.end()) ;
	reverse(vp.begin() , vp.end()) ;
	long long ans = 0 ;
	for(auto &p : vp)
	{
		int node = p.second ;
		for(auto &child : adj[node])
		{
			ans += arr[node] + dfs(child , node) ;
			adj[child].erase(node) ;
		}
	}
	return cout<<ans<<"\n" , 0 ;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 3 ms 4972 KB Output is correct
5 Correct 3 ms 4972 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 18152 KB Output is correct
2 Correct 70 ms 14828 KB Output is correct
3 Correct 64 ms 14188 KB Output is correct
4 Correct 77 ms 16360 KB Output is correct
5 Correct 124 ms 20328 KB Output is correct
6 Execution timed out 1083 ms 22376 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 3 ms 4972 KB Output is correct
5 Correct 3 ms 4972 KB Output is correct
6 Correct 6 ms 5100 KB Output is correct
7 Correct 6 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 8 ms 5100 KB Output is correct
10 Correct 8 ms 5100 KB Output is correct

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 3 ms 4972 KB Output is correct
5 Correct 3 ms 4972 KB Output is correct
6 Correct 98 ms 18152 KB Output is correct
7 Correct 70 ms 14828 KB Output is correct
8 Correct 64 ms 14188 KB Output is correct
9 Correct 77 ms 16360 KB Output is correct
10 Correct 124 ms 20328 KB Output is correct
11 Execution timed out 1083 ms 22376 KB Time limit exceeded
12 Halted 0 ms 0 KB -