Submission #833942

#	Time	Username	Problem	Language	Result	Execution time	Memory
833942		MilosMilutinovic	Magic Tree (CEOI19_magictree)	C++14	18 / 100	380 ms	1048576 KiB

magictree

/**
 *    author:  wxhtzdy
 *    created: 22.08.2023 09:39:57
**/
#include <bits/stdc++.h>

using namespace std;

const int MAX = 100010;
const int C = 40;

int root[MAX], ls[MAX * C], rs[MAX * C], tsz;
long long sum[MAX * C];

void Modify(int& v, int p, int l, int r, int i, long long x) {
  v = ++tsz;
  ls[v] = ls[p];
  rs[v] = rs[p];
  sum[v] = sum[p] + x;
  if (l == r) {
    return;
  }      
  int mid = l + r >> 1;
  if (i <= mid) {
    Modify(ls[v], ls[p], l, mid, i, x);
  } else {
    Modify(rs[v], rs[p], mid + 1, r, i, x);
  }
}

long long Query(int v, int l, int r, int ll, int rr) {
  if (l > r || l > rr || r < ll || ll > rr) {
    return 0LL;
  }           
  if (ll <= l && r <= rr) {
    return sum[v];
  }
  int mid = l + r >> 1;
  return Query(ls[v], l, mid, ll, rr) + Query(rs[v], mid + 1, r, ll, rr);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    --p;
    g[p].push_back(i);
  }
  vector<int> x(n, -1), y(n);
  for (int i = 0; i < m; i++) {
    int v, d, w;
    cin >> v >> d >> w;
    --v;
    x[v] = d;
    assert(1 <= x[v] && x[v] <= k);
    y[v] = w;
  }
  vector<vector<long long>> dp(n, vector<long long>(k));
  vector<vector<int>> dd(n);
  vector<int> f(n);
  auto GetDp = [&](int rt, int p) {
    return Query(root[rt], 1, k, 1, p);
  };
  function<void(int)> Solve = [&](int v) {
    f[v] = v;    
    for (int u : g[v]) {
      Solve(u);
      if ((int) dd[f[u]].size() > (int) dd[f[v]].size()) {
        //f[v] = f[u];        
      }
    }
    for (int u : g[v]) {
      if (f[v] == f[u]) {
        continue;
      }                
      sort(dd[f[u]].begin(), dd[f[u]].end());
      dd[f[u]].erase(unique(dd[f[u]].begin(), dd[f[u]].end()), dd[f[u]].end());
      for (int j = 1; j < (int) dd[f[u]].size(); j++) {
        assert(dd[f[u]][j] > dd[f[u]][j - 1]);
      }
      int sz = (int) dd[f[u]].size();
      vector<int> stk;
      for (int j = 0; j < sz; j++) {
        if (stk.empty() || GetDp(f[u], dd[f[u]][stk.back()]) < GetDp(f[u], dd[f[u]][j])) {
          stk.push_back(j);
        }
      }                   
      sz = (int) stk.size();
      for (int j = 0; j < sz; j++) {
        long long dp_val = GetDp(f[u], dd[f[u]][stk[j]]);
        Modify(root[f[v]], root[f[v]], 1, k, dd[f[u]][stk[j]], dp_val);
        if (j != sz - 1) {
          Modify(root[f[v]], root[f[v]], 1, k, dd[f[u]][stk[j + 1]], -dp_val);
        }
      }
      /* long long mx = 0;
      for (int j = 1; j <= k; j++) {
        mx = max(mx, GetDp(f[u], j));
        Modify(root[f[v]], root[f[v]], 1, k, j, mx);
        if (j != k) {
          Modify(root[f[v]], root[f[v]], 1, k, j + 1, -mx);
        }
      } */
      for (int x : dd[f[u]]) {
        dd[f[v]].push_back(x);
      }
    }       
    /* for (int u : g[v]) {
      for (int i = 0; i < k; i++) {
        long long mx = 0;
        for (int j = 0; j <= i; j++) {
          mx = max(mx, dp[u][j]);
        }
        dp[v][i] += mx;
      }
    } */
    if (x[v] != -1) {
//      dp[v][x[v]] += y[v];
      Modify(root[f[v]], root[f[v]], 1, k, x[v], y[v]);
      if (x[v] != k) {
        Modify(root[f[v]], root[f[v]], 1, k, x[v] + 1, -y[v]);
      }
      dd[f[v]].push_back(x[v]);
    }
  };
  Solve(0); 
  long long ans = 0;
  for (int i = 1; i <= k; i++) {
    ans = max(ans, GetDp(f[0], i));
  }
  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'void Modify(int&, int, int, int, int, long long int)':
magictree.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int mid = l + r >> 1;
      |             ~~^~~
magictree.cpp: In function 'long long int Query(int, int, int, int, int)':
magictree.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~

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