Submission #661286

#	Time	Username	Problem	Language	Result	Execution time	Memory
661286		Kenpar	Sjekira (COCI20_sjekira)	C++17	40 / 110	1086 ms	12188 KiB

sjekira

#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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60