Submission #1154062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154062		justin271828	Sjekira (COCI20_sjekira)	C++20	0 / 110	55 ms	6212 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;

#define l2 long long
#define li pair<l2, int>
#define f first
#define s second

int main() {
  int n;
  cin >> n;
  li arr[n];
  l2 mem[n];
  for (int i = 0; i < n; i++) {
    cin >> arr[i].f;
    mem[i] = arr[i].f;
    arr[i].s = i;
  }
  sort(arr, arr+n);
  vector<int> v[n];
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (mem[a] < mem[b] || (mem[a] == mem[b] && a < b)) v[a].push_back(b);
    else v[b].push_back(a);
  }
  int ufds[n];
  for (int i = 0; i < n; i++) ufds[i] = i;
  int ans = 0;
  for (li p: arr) {
    for (int k: v[p.s]) {
      int a = p.s;
      int b = k;
      int da = 0;
      int db = 0;
      while (a != ufds[a]) {
        a = ufds[a];
        da++;
      }
      while (b != ufds[b]) {
        b = ufds[b];
        db++;
      }
      ans += mem[a];
      ans += mem[b];
      if (da < db) {
        mem[b] = max(mem[a], mem[b]);
        ufds[a] = ufds[b];}
      else {
        mem[a] = max(mem[a], mem[b]);
        ufds[b] = ufds[a];}
    }
  }
  cout << ans;
  return 0;
}

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