oj.uz

Submission #833942

# Submission time Handle Problem Language Result Execution time Memory
833942 2023-08-22T09:40:30 Z MilosMilutinovic Magic Tree (CEOI19_magictree) C++14
18 / 100
 380 ms 1048576 KB 
/**
 *    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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 368 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 380 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10452 KB Output is correct
2 Correct 39 ms 17880 KB Output is correct
3 Runtime error 144 ms 146964 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 25996 KB Output is correct
2 Correct 69 ms 21728 KB Output is correct
3 Correct 89 ms 39584 KB Output is correct
4 Correct 65 ms 24552 KB Output is correct
5 Correct 68 ms 52856 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 368 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 135 ms 80344 KB Output is correct
11 Correct 106 ms 57804 KB Output is correct
12 Runtime error 202 ms 207372 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 305 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 368 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 32 ms 10452 KB Output is correct
11 Correct 39 ms 17880 KB Output is correct
12 Runtime error 144 ms 146964 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 368 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Runtime error 380 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -