Submission #332557

#	Time	Username	Problem	Language	Result	Execution time	Memory
332557		morato	Sjekira (COCI20_sjekira)	C++17	0 / 110	49 ms	14824 KiB

sjekira

/**
 *    author:  morato
 *    created: 02.12.2020 18:17:53
**/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector<int> adj[N];
vector<int> sub[N];
int p[N], pivo;

bool cmp(int a, int b) {
  return p[a] > p[b];
}

void dfs(int v, int g = -1, int pp = -1) {
  for (int u : adj[v]) if (u != pp) {
    if (v == pivo) g++;
    sub[g].push_back(u);
    dfs(u, g, v);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    if (p[i] > mx) {
      mx = p[i];
      pivo = i;
    }
  }
  int G = 0;
  for (int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    if (a == pivo || b == pivo) G++;
  }
  dfs(pivo);
  long long ans = 0;
  for (int i = 0; i < G; i++) {
    sort(sub[i].begin(), sub[i].end(), cmp);
    ans += 1ll * p[pivo] + p[sub[i][0]];
    for (int j = 1; j < (int) sub[i].size(); j++) {
      ans += 1ll * p[sub[i][j - 1]] + p[sub[i][j]];
    }
  }
  cout << ans << '\n';
  return 0;
}

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