oj.uz

Submission #659877

# Submission time Handle Problem Language Result Execution time Memory
659877 2022-11-19T15:46:16 Z 600Mihnea Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 19376 KB 
bool home = 0;
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int) 1e5 + 7;
int n;
int m;
int k;
int p[N];
int type[N];
int w[N];
int sub[N];
int bg[N];
ll delta[N];
vector<int> g[N];

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

vector<pair<int, ll>> get_and_clr_dp() {
  vector<pair<int, ll>> sol;
  for (int i = 1; i <= k; i++) {
    if (delta[i]) {
      sol.push_back({i, delta[i]});
      delta[i] = 0;
    }
  }
  return sol;
}

ll dpaux[N];

void solve(int a) {
  if (g[a].empty()) {
    if (type[a]) {
      delta[type[a]] += w[a];
    }
  } 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());
        continue;
      }
    }
    {
      int b = bg[a];
      solve(b);
      for (auto &v : all) {

        for (auto &g : v) {
          delta[g.first] += g.second;
        }
      }
      if (type[a]) {
        delta[type[a]] += w[a];
        delta[type[a] + 1] -= w[a];
        ll mx = 0, cur = 0;
        for (int i = 1; i <= k; i++) {
          cur += delta[i];
          delta[i] = max(mx, cur) - mx;
          mx = max(mx, cur);
        }
      }
    }
  }
//  cout << a << " : ";
  ll sol = 0;
  for (int i = 1; i <= k; i++) {
    sol += delta[i];
  //  cout << sol << " ";
  }
 // cout << "\n";
}

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


  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];
  }
  bu(1);
  solve(1);
  ll sol = 0;
  for (int i = 1; i <= k; i++) {
    sol += delta[i];
  }
  cout << sol << "\n";
  return 0;
}
/**

dp[vertex][last_value] = ?



**/

Compilation message

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

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 7364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2800 KB Output is correct
4 Execution timed out 2080 ms 19376 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6244 KB Output is correct
2 Correct 49 ms 6204 KB Output is correct
3 Correct 44 ms 12100 KB Output is correct
4 Correct 34 ms 9804 KB Output is correct
5 Correct 45 ms 18688 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2616 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 50 ms 6228 KB Output is correct
11 Correct 47 ms 6236 KB Output is correct
12 Correct 42 ms 12100 KB Output is correct
13 Correct 33 ms 9756 KB Output is correct
14 Correct 41 ms 18636 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 4012 KB Output is correct
2 Correct 1236 ms 6748 KB Output is correct
3 Execution timed out 2021 ms 6952 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2616 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2800 KB Output is correct
13 Execution timed out 2080 ms 19376 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2616 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Execution timed out 2081 ms 7364 KB Time limit exceeded
11 Halted 0 ms 0 KB -