Submission #1153952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153952		YSH2020	Sjekira (COCI20_sjekira)	C++20	0 / 110	115 ms	23992 KiB

sjekira

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
  int l, r, m, val = 0;
  node *lf = nullptr; node *rg = nullptr;
  
  node (int _l, int _r): l(_l), r(_r), m((_l+_r)/2) {}
  int qry(int x, int y) {
    if (r < x || l > y) return 0;
    if (x <= l && r <= y) return val;
    if (!lf) create();
    return max(lf->qry(x, y), rg->qry(x, y));
  }
  void upd(int pos, int v) {
    if (l == r) {val = v; return;}
    if (!lf) create();
    if (pos <= m) lf->upd(pos, v);
    else rg->upd(pos, v);
    val = max(lf->val, rg->val);
  }
  void create() {
    if (l != r) {
      lf = new node(l, m);
      rg = new node(m+1, r);
    }
  }
}*root;


int cost[100005];
vector<int> adj[100005];
pair<int, int> ord[100005];
int x;
int par[100005];
void dfs(int n, int p) {
  par[n] = p;
  x++;
  ord[n].first = x;
  for (auto i:adj[n]) {
    if (i != p) {
      dfs(i, n);
    }
  }
  ord[n].second = x;
}

signed main() {
  int ans = 0;
  int n; cin >> n;
  for (int i = 0; i < n; i++) cin >> cost[i];
  for (int i = 0; i < n-1; i++) {
    int x, y; cin >> x >> y;
    x--; y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  x = -1;
  dfs(0, -1);
  root = new node(0, n);
  for (int i = 0; i < n; i++) root->upd(ord[i].first, cost[i]);
  priority_queue<pair<int,int>> pq;
  for (int i = 0; i < n; i++) pq.push(make_pair(cost[i], i));
  for (int i = 0; i < n; i++) {
    auto tmp = pq.top();
    pq.pop();
    for (auto x:adj[tmp.second]) {
      if (x != par[tmp.second]) {
        if (cost[x] < tmp.first) {
          ans += root->qry(ord[x].first, ord[x].second)+tmp.first;
        }
      }
      else {
        if (cost[x] < tmp.first) {
          ans += max(root->qry(0, ord[x].first-1), root->qry(ord[x].second, n))+tmp.first;
        }
      }
    }
    root->upd(tmp.second, 0);
  }
  cout << ans;
}

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