oj.uz

Submission #659876

# Submission time Handle Problem Language Result Execution time Memory
659876 2022-11-19T15:42:38 Z 600Mihnea Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 22132 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]) {
        for (int i = 1; i <= k; i++) {
          dpaux[i] = dpaux[i - 1] + delta[i];
        }
        dpaux[type[a]] += w[a];
        for (int i = 1; i <= k; i++) {
          dpaux[i] = max(dpaux[i - 1], dpaux[i]);
        }
        for (int i = 1; i <= k; i++) {
          delta[i] = dpaux[i] - dpaux[i - 1];
        }
      }
    }
  }
//  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:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     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 2 ms 2680 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2772 KB Output is correct
2 Correct 6 ms 2772 KB Output is correct
3 Correct 5 ms 2820 KB Output is correct
4 Execution timed out 2081 ms 22132 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6252 KB Output is correct
2 Correct 57 ms 6196 KB Output is correct
3 Correct 46 ms 12112 KB Output is correct
4 Correct 35 ms 9744 KB Output is correct
5 Correct 46 ms 18616 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 2 ms 2680 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 51 ms 7628 KB Output is correct
11 Correct 52 ms 7648 KB Output is correct
12 Correct 48 ms 13508 KB Output is correct
13 Correct 37 ms 10888 KB Output is correct
14 Correct 51 ms 20200 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 4468 KB Output is correct
2 Correct 1359 ms 7884 KB Output is correct
3 Correct 1996 ms 8472 KB Output is correct
4 Execution timed out 2057 ms 8348 KB Time limit exceeded
5 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 2 ms 2680 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 5 ms 2772 KB Output is correct
11 Correct 6 ms 2772 KB Output is correct
12 Correct 5 ms 2820 KB Output is correct
13 Execution timed out 2081 ms 22132 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 2 ms 2680 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Execution timed out 2090 ms 7396 KB Time limit exceeded
11 Halted 0 ms 0 KB -