oj.uz

답안 #661286

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
661286 2022-11-25T09:14:36 Z Kenpar Sjekira (COCI20_sjekira) C++17
40 / 110
 1000 ms 12188 KB 
#include "bits/stdc++.h"
using namespace std;

#define ll long long
#define endl '\n'

const ll MOD = 1e9+7;
const ll INF = 1e16;
const ll MAX = 1e5;
vector<vector<int>> edges(MAX);
vector<int> weight(MAX);

vector<bool> visited(MAX, false);

int DFS(int cur){

	if(visited[cur]) return 0;
	visited[cur] = true;
	int ma = weight[cur];

	for(int a : edges[cur]){
		ma = max(ma, DFS(a));
	}

	return ma;
}

void solve(){
	int n;
	cin>>n;

	vector<pair<int,int>> sorted(n); 
	for(int i = 0; i < n; i++){
		cin>>weight[i];
		sorted[i] = {weight[i], i};
	}

	sort(sorted.begin(), sorted.end(), greater<pair<int,int>>());

	for(int i = 0; i < n-1; i++){
		int a,b; cin>>a>>b;
		a--,b--;

		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	ll ans = 0;
	for(pair<int,int> zort : sorted){
		int cur = zort.second;
		visited[cur] = true;
		vector<bool> temp = visited;
		for(int tar : edges[cur]){
			int zz = DFS(tar);
			if(zz == 0) continue;

			ans+= zort.first + zz;
			visited = temp;
		}
	}

	cout<<ans;
}	 

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(NULL);
    int t = 1;

    //cin>>t;
    int sorted = t;
    while(t--){
        //cout<<"Case #"<<sorted - t<<" > "<<endl;
        solve();

        cout<<endl;
    }

    cout.flush();
}

Compilation message

sjekira.cpp: In function 'int main()':
sjekira.cpp:72:9: warning: unused variable 'sorted' [-Wunused-variable]
   72 |     int sorted = t;
      |         ^~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 9980 KB Output is correct
2 Correct 96 ms 8056 KB Output is correct
3 Correct 86 ms 7712 KB Output is correct
4 Correct 97 ms 8948 KB Output is correct
5 Correct 153 ms 10860 KB Output is correct
6 Execution timed out 1086 ms 12188 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

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

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 134 ms 9980 KB Output is correct
7 Correct 96 ms 8056 KB Output is correct
8 Correct 86 ms 7712 KB Output is correct
9 Correct 97 ms 8948 KB Output is correct
10 Correct 153 ms 10860 KB Output is correct
11 Execution timed out 1086 ms 12188 KB Time limit exceeded
12 Halted 0 ms 0 KB -