Submission #891700

#	Time	Username	Problem	Language	Result	Execution time	Memory
891700		ind1v	Sjekira (COCI20_sjekira)	C++11	110 / 110	41 ms	9584 KiB

sjekira

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

struct dsu {
  int lab[N];
  int mx[N];
  
  dsu() {
    memset(lab, -1, sizeof(lab));
    memset(mx, -1, sizeof(mx));
  }
  
  int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  }
  
  bool merge(int u, int v) {
    if ((u = find(u)) == (v = find(v))) {
      return false;
    }
    if (lab[u] > lab[v]) {
      swap(u, v);
    }
    lab[u] += lab[v];
    lab[v] = u;
    mx[u] = max(mx[u], mx[v]);
    return true;
  }
};

int n;
int t[N];
int ord[N];
bool on[N];
vector<int> g[N];
dsu d;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> t[i];
  }
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    cin >> x >> y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  iota(ord + 1, ord + n + 1, 1);
  sort(ord + 1, ord + n + 1, [](int &u, int &v) -> bool {
    return t[u] < t[v];
  });
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    d.mx[ord[i]] = t[ord[i]];
    for (int j : g[ord[i]]) {
      if (on[j]) {
        ans += d.mx[d.find(j)];
        ans += t[ord[i]];
        d.merge(ord[i], j);
      }
    }
    on[ord[i]] = true;
  }
  cout << ans << '\n';
  return 0;
}

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