oj.uz

Submission #659893

# Submission time Handle Problem Language Result Execution time Memory
659893 2022-11-19T16:22:44 Z 600Mihnea Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 36120 KB 
bool home = 0;
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int) 1e5 + 7;
const ll INF = (ll) 1e18 + 7;
int n;
int m;
int k;
int p[N];
int type[N];
int w[N];
int sub[N];
int bg[N];
ll dp[N];
int low[N];
int high[N];
int ord[N];
int top;
vector<int> g[N];
int Counter = 0;
int last_seen[N];

ll tree[4 * N];
ll lazy_a[4 * N];
ll lazy_b[4 * N];
ll lazy_max[4 * N];

void push(int v, int tl, int tr) {
  if (lazy_a[v] != 1 || lazy_b[v] != 0) {
    tree[v] = tree[v] * lazy_a[v] + lazy_b[v];
    if (tl < tr) {
      for (int v2 = 2 * v; v2 <= 2 * v + 1; v2++) {
        lazy_a[v2] *= lazy_a[v];
        lazy_b[v2] *= lazy_a[v];
        lazy_b[v2] += lazy_b[v];
        lazy_max[v2] = lazy_max[v2] * lazy_a[v] + lazy_b[v];
      }
    }
    lazy_a[v] = 1;
    lazy_b[v] = 0;
  }
  if (lazy_max[v]) {
    tree[v] = max(tree[v], lazy_max[v]);
    if (tl < tr) {
      for (int v2 = 2 * v; v2 <= 2 * v + 1; v2++) {
        lazy_max[v2] = max(lazy_max[v2], lazy_max[v]);
      }
    }
    lazy_max[v] = 0;
  }
}

void pushcoef(int v, int tl, int tr, int l, int r, ll a, ll b) {
  push(v, tl, tr);
  if (tr < l || r < tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    lazy_a[v] = a;
    lazy_b[v] = b;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  pushcoef(2 * v, tl, tm, l, r, a, b);
  pushcoef(2 * v + 1, tm + 1, tr, l, r, a, b);
  tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}

void maxup(int v, int tl, int tr, int l, int r, ll x) {
  push(v, tl, tr);
  if (tr < l || r < tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    lazy_max[v] = x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  maxup(2 * v, tl, tm, l, r, x);
  maxup(2 * v + 1, tm + 1, tr, l, r, x);
  tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}

ll get_max(int v, int tl, int tr, int l, int r) {
  push(v, tl, tr);
  if (tr < l || r < tl) {
    return -INF;
  }
  if (l <= tl && tr <= r) {
    return tree[v];
  }
  int tm = (tl + tr) / 2;
  return max(get_max(2 * v, tl, tm, l, r), get_max(2 * v + 1, tm + 1, tr, l, r));
}

void pushcoef(int l, int r, ll a, ll b) {
  pushcoef(1, 1, k, l, r, a, b);
}

void maxup(int l, int r, ll x) {
  maxup(1, 1, k, l, r, x);
}

ll get_max(int l, int r) {
  if (l > r) {
    return 0;
  }
  if (l == 0) {
    assert(r == 0);
    return 0;
  }
  assert(1 <= l && l <= r && r <= k);
  return get_max(1, 1, k, l, r);
}

void bu(int a) {
  low[a] = ++top;
  ord[top] = a;
  sub[a] = 1;
  for (auto &b : g[a]) {
    bu(b);
    sub[a] += sub[b];
    if (sub[b] > sub[bg[a]]) {
      bg[a] = b;
    }
  }
  high[a] = top;
}


vector<pair<int, ll>> get_and_clr_dp(int v) {
  Counter++;
  vector<pair<int, ll>> sol;
  for (int j = low[v]; j <= high[v]; j++) {
    if (int i = type[ord[j]]) {
      if (last_seen[i] == Counter) {
        continue;
      }
      last_seen[i] = Counter;
      assert(dp[i] == get_max(i, i));
      assert(dp[i - 1] == get_max(i - 1, i - 1));
      sol.push_back({i, dp[i] - dp[i - 1]});
    }
  }
  /*for (int i = 1; i <= n; i++) cout << dp[i] << " "; cout << "\n";
  for (int i = 1; i <= n; i++) cout << get_max(i, i) << " "; cout << "\n";
  cout << " ---------------------- \n";*/
  for (int i = 1; i <= k; i++) {
    dp[i] = 0;
  }
  pushcoef(1, k, 0, 0);
  return sol;
}

ll dpaux[N];

void solve(int a) {
  if (g[a].empty()) {
    if (type[a]) {
      /*for (int i = 1; i <= n; i++) cout << dp[i] << " "; cout << "\n";
      for (int i = 1; i <= n; i++) cout << get_max(i, i) << " "; cout << "\n";
      cout << " ----------------------a \n";*/
      pushcoef(type[a], k, 1, w[a]);
      for (int j = type[a]; j <= k; j++) {
        dp[j] += w[a];
      }
      /*for (int i = 1; i <= n; i++) cout << dp[i] << " "; cout << "\n";
      for (int i = 1; i <= n; i++) cout << get_max(i, i) << " "; cout << "\n";
      cout << " ----------------------a \n";
      cout << " ############################## \n";*/
    }
  } else {
    assert(bg[a] != -1);
    vector<vector<pair<int, ll>>> all;
    for (auto &b : g[a]) {
      if (b != bg[a]) {
        solve(b);
        all.push_back(get_and_clr_dp(b));
        continue;
      }
    }
    {
      int b = bg[a];
      solve(b);
      for (auto &v : all) {
        for (auto &g : v) {
          pushcoef(g.first, k, 1, g.second);
          for (int j = g.first; j <= k; j++) {
            dp[j] += g.second;
          }
          /*for (int i = 1; i <= n; i++) cout << dp[i] << " "; cout << "\n";
          for (int i = 1; i <= n; i++) cout << get_max(i, i) << " "; cout << "\n";
          cout << " ----------------------b \n";*/
        }
      }
      if (type[a]) {
        dp[type[a]] += w[a];
        pushcoef(type[a], type[a], 1, w[a]);
        maxup(type[a], k, dp[type[a]]);
        for (int j = type[a]; j <= k; j++) {
          dp[j] = max(dp[j], dp[j - 1]);
        }
        /*for (int i = 1; i <= n; i++) cout << dp[i] << " "; cout << "\n";
        for (int i = 1; i <= n; i++) cout << get_max(i, i) << " "; cout << "\n";
        cout << " ----------------------c \n";*/
      }
    }
  }
}

int main() {

  if (!home) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen("input.txt", "r", stdin);
  }


  for (int i = 0; i < 4 * N; i++) {
    lazy_a[i] = 1;
    lazy_b[i] = 0;
    lazy_max[i] = 0;
  }

  cin >> n >> m >> k;
  if (0) {
    cout << "  : ";
    for (int i = 1; i <= k; i++) {
      cout << i << " ";
    }
    cout << "\n";
  }
  for (int i = 2; i <= n; i++) {
    cin >> p[i];
    g[p[i]].push_back(i);
  }
  for (int i = 1; i <= m; i++) {
    int v;
    cin >> v;
    cin >> type[v];
    cin >> w[v];
  }
  {
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
      if (type[i]) {
        mp[type[i]] = 0;
      }
    }
    int cr = 0;
    for (auto &it : mp) {
      it.second = ++cr;
    }
    for (int i = 1; i <= n; i++) {
      if (type[i]) {
        type[i] = mp[type[i]];
      }
    }
    k = min(k, m);
  }
  bu(1);
  solve(1);
  assert(dp[k] == get_max(1, k));
  cout << dp[k] << "\n";
  return 0;
}
/**

dp[vertex][last_value] = ?



**/

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:222:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  222 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12112 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 6 ms 12084 KB Output is correct
5 Correct 6 ms 12064 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1383 ms 18508 KB Output is correct
2 Correct 488 ms 24168 KB Output is correct
3 Execution timed out 2075 ms 21072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 7 ms 12244 KB Output is correct
3 Correct 7 ms 12244 KB Output is correct
4 Execution timed out 2084 ms 36120 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 16788 KB Output is correct
2 Correct 80 ms 16788 KB Output is correct
3 Correct 64 ms 23948 KB Output is correct
4 Correct 51 ms 20296 KB Output is correct
5 Correct 53 ms 32392 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12112 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 6 ms 12084 KB Output is correct
5 Correct 6 ms 12064 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 118 ms 16844 KB Output is correct
11 Correct 106 ms 16784 KB Output is correct
12 Correct 76 ms 23940 KB Output is correct
13 Correct 88 ms 20324 KB Output is correct
14 Correct 67 ms 32316 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 13140 KB Output is correct
2 Correct 51 ms 16888 KB Output is correct
3 Correct 46 ms 16856 KB Output is correct
4 Correct 53 ms 16900 KB Output is correct
5 Correct 37 ms 18760 KB Output is correct
6 Correct 65 ms 20392 KB Output is correct
7 Correct 40 ms 23728 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12112 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 6 ms 12084 KB Output is correct
5 Correct 6 ms 12064 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Execution timed out 2084 ms 36120 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12112 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 6 ms 12084 KB Output is correct
5 Correct 6 ms 12064 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 1383 ms 18508 KB Output is correct
11 Correct 488 ms 24168 KB Output is correct
12 Execution timed out 2075 ms 21072 KB Time limit exceeded
13 Halted 0 ms 0 KB -