Submission #1198040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198040		LucaLucaM	Magic Tree (CEOI19_magictree)	C++20	100 / 100	1042 ms	544096 KiB

magictree

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
 
using ll = long long;
#define debug(x) #x << " = " << x << '\n'
 
struct Fruit {
  int d, w;
};
 
const int NMAX = 1e5;
const int DMAX = 1e5 + 7;
 
std::vector<int> g[NMAX + 1];
 
Fruit a[NMAX + 1];
 
std::set<int> timeStamps[NMAX + 1];
 
struct Brut {
  ll value[DMAX + 1];
  Brut() {
    for (int i = 0; i <= DMAX; i++) {
      value[i] = 0;
    }
  }
  void init(int n) {
    for (int i = 1; i <= DMAX; i++) {
      value[i] = 0;
    }
  }
  void rangeAdd(int l, int r, ll x) {
    for (int i = l; i <= r; i++) {
      value[i] += x;
    }
  }
  void setValue(int p, ll x) {
    value[p] = x;
  }
  void add(int p, ll x) {
    value[p] += x;
  }
  ll query(int p) {
    if (p == 0) {
      assert(value[p] == 0);
    }
    return value[p];
  }
  int findNextGr(int p, ll x) {
    while (p <= DMAX && value[p] <= x) {
      p++;
    }
    return p;
  }
  void rangeSet(int l, int r, ll x) {
    for (int i = l; i <= r; i++) {
      value[i] = x;
    }
  }
};
 
struct Segtree {
  struct Node {
    ll maxi;
    ll lazyAdd;
    ll lazySet;
    Node* l;
    Node* r;
    Node() : maxi(0), lazyAdd(0), lazySet(0), l(nullptr), r(nullptr) {}
    Node(ll x) : maxi(x), lazyAdd(0), lazySet(0), l(nullptr), r(nullptr) {}
    void refresh() {
      maxi = 0;
      if (l != nullptr) {
        maxi = std::max(maxi, l -> maxi);
      }
      if (r != nullptr) {
        maxi = std::max(maxi, r -> maxi);
      }
      lazyAdd = lazySet = 0;
    }
  };
 
  int n;
  Node* root;
 
  void init(int _n) {
    n = _n + 2;
    root = new Node();
  }
  void kill(Node* &root) {
    if (root -> l != nullptr) {
      kill(root -> l);
    }
    if (root -> r != nullptr) {
      kill(root -> r);
    }
    delete(root);
  }
  void kill() {
    kill(root);
  }
  void push(Node* &node, int tl, int tr) {
    if (node == nullptr)  {
      node = new Node();
    }
    if (tl != tr) {
      if (node -> l == nullptr) {
        node -> l = new Node();
      }
      if (node -> r == nullptr) {
        node -> r = new Node();
      }
      if (node -> lazySet != 0) {
        node -> l -> lazySet = node -> lazySet;
        node -> l -> lazyAdd = 0;
        node -> r -> lazySet = node -> lazySet;
        node -> r -> lazyAdd = 0;
      } 
      node -> l -> lazyAdd += node -> lazyAdd;
      node -> r -> lazyAdd += node -> lazyAdd;
    }
    if (node -> lazySet != 0) {
      node -> maxi = node -> lazySet;
    }
    node -> maxi += node -> lazyAdd;
    node -> lazySet = 0;
    node -> lazyAdd = 0;
  }
 
  void rangeAdd(Node* &node, int tl, int tr, int l, int r, ll x) {
    if (node == nullptr) {
      node = new Node();
    }
    push(node, tl, tr);
    if (l <= tl && tr <= r) {
      node -> lazyAdd += x;
    } else {
      if (node -> l == nullptr) {
        node -> l = new Node();
      }
      if (node -> r == nullptr) {
        node -> r = new Node();
      }
      int mid = (tl + tr) / 2;
      if (l <= mid) {
        rangeAdd(node -> l, tl, mid, l, r, x);
      }
      if (mid < r) {
        rangeAdd(node -> r, mid + 1, tr, l, r, x);
      }
      push(node -> l, tl, mid);
      push(node -> r, mid + 1, tr);
      node -> refresh();
      // node -> maxi = std::max(node -> l -> maxi, node -> r -> maxi);
    }
  }
 
  void rangeSet(Node* &node, int tl, int tr, int l, int r, ll x) {
    if (node == nullptr) {
      node = new Node();
    }
    push(node, tl, tr);
    if (l <= tl && tr <= r) {
      node -> lazySet = x;
    } else {
      if (node -> l == nullptr) {
        node -> l = new Node();
      }
      if (node -> r == nullptr) {
        node -> r = new Node();
      }
      int mid = (tl + tr) / 2;
      if (l <= mid) {
        rangeSet(node -> l, tl, mid, l, r, x);
      }
      if (mid < r) {
        rangeSet(node -> r, mid + 1, tr, l, r, x);
      }
      push(node -> l, tl, mid);
      push(node -> r, mid + 1, tr);
      node -> refresh();
    }
  }
  ll query(Node* &node, int tl, int tr, int p) {
    if (node == nullptr) {
      node = new Node();
    }
    push(node, tl, tr);
    if (tl == tr) {
      return node -> maxi;
    } else {
      int mid = (tl + tr) / 2;
      if (p <= mid) {
        if (node -> l == nullptr) {
          node -> l = new Node();
        }
        return query(node -> l, tl, mid, p);
      } else {
        if (node -> r == nullptr) {
          node -> r = new Node();
        }
        return query(node -> r, mid + 1, tr, p);
      }
    }
  }
 
  void rangeAdd(int l, int r, ll x) {
    if (l > r) {
      return;
    }
    rangeAdd(root, 0, n, l, r, x);
  }
  void rangeSet(int l, int r, ll x) {
    if (l > r) {
      return;
    }
    rangeSet(root, 0, n, l, r, x);
  }
  ll query(int p) {
    return query(root, 0, n, p);
  }
 
  int findNextGr(Node* &node, int tl, int tr, ll x) {
    if (node == nullptr) {
      node = new Node();
    }
    push(node, tl, tr);
    if (node -> maxi <= x) {
      return -1;
    }
    if (tl == tr) {
      return tl;
    }
    int mid = (tl + tr) / 2;
    int aux = findNextGr(node -> l, tl, mid, x);
    if (aux != -1) {
      return aux; 
    }
    return findNextGr(node -> r, mid + 1, tr, x);
  }
 
  int findNextGr(int p, ll x) {
    int q = findNextGr(root, 0, n, x);
    if (q == -1) {
      return DMAX + 1;
    }
    return q;
  }
 
  ll queryMax() {
    push(root, 0, n);
    return root -> maxi;
  }
};
 
// pun query pe u si dupa fac un max= da asta pare cam greu
// in schimb cealalta chestie ce face e asa:
// tin intervalele consecutive de valori egale
// fac += pe niste pozitii
 
Segtree DS[NMAX + 1];
 
void dfs(int u) {
  int heavySon = 0;
  for (const auto &v : g[u]) {
    dfs(v);
    if (heavySon == 0 || (int) timeStamps[v].size() > (int) timeStamps[heavySon].size()) {
      heavySon = v;
    }
  }
 
  if (heavySon) {
    std::swap(timeStamps[u], timeStamps[heavySon]);
    std::swap(DS[u], DS[heavySon]);
  } else {
    DS[u].init(DMAX + 1);
    timeStamps[u].insert(0);
    timeStamps[u].insert(DMAX + 1);
  }
  
  timeStamps[u].insert(a[u].d);
 
  for (const auto &v : g[u]) {
    if (v != heavySon) {
      int tprev = 0;
      ll vprev = 0;
      for (int t : timeStamps[v]) {
        DS[u].rangeAdd(tprev, t - 1, vprev);
        vprev = DS[v].query(t);
        tprev = t;
        timeStamps[u].insert(t);
      }
      timeStamps[v].clear();
      DS[v].kill();
    }
  }
 
  if (a[u].d != 0) {
    ll value = DS[u].query(a[u].d) + a[u].w;
    int p = DS[u].findNextGr(a[u].d, value);
    DS[u].rangeSet(a[u].d, p - 1, value);
  }
}
 
int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
 
  int n, m, k;
  std::cin >> n >> m >> k;
 
  for (int i = 2; i <= n; i++) {
    int p;
    std::cin >> p;
    g[p].push_back(i);
  }
 
  for (int i = 1; i <= n; i++) {
    a[i].d = a[i].w = 0;
  }
  
  for (int i = 0; i < m; i++) {
    int u;
    std::cin >> u;
    std::cin >> a[u].d >> a[u].w;
  }
  
  dfs(1);
  
  std::cout << DS[1].queryMax();
  
  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17