oj.uz

Submission #659886

# Submission time Handle Problem Language Result Execution time Memory
659886 2022-11-19T15:59:37 Z 600Mihnea Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 23400 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 dp[N];
int low[N];
int high[N];
int ord[N];
int top;
vector<int> g[N];
int Counter = 0;
int last_seen[N];

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;
      sol.push_back({i, dp[i] - dp[i - 1]});
    }
  }
  for (int i = 1; i <= k; i++) {
    dp[i] = 0;
  }
  return sol;
}

ll dpaux[N];

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

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];
  }
  {
    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);
  cout << dp[k] << "\n";
  return 0;
}
/**

dp[vertex][last_value] = ?



**/

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 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 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 Correct 1197 ms 8560 KB Output is correct
2 Correct 402 ms 13172 KB Output is correct
3 Execution timed out 2083 ms 10196 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Execution timed out 2086 ms 23400 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7396 KB Output is correct
2 Correct 53 ms 7384 KB Output is correct
3 Correct 49 ms 13268 KB Output is correct
4 Correct 38 ms 10916 KB Output is correct
5 Correct 43 ms 19796 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 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 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 59 ms 7444 KB Output is correct
11 Correct 56 ms 7364 KB Output is correct
12 Correct 48 ms 13260 KB Output is correct
13 Correct 41 ms 10928 KB Output is correct
14 Correct 46 ms 19788 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3668 KB Output is correct
2 Correct 52 ms 7468 KB Output is correct
3 Correct 47 ms 7380 KB Output is correct
4 Correct 54 ms 7384 KB Output is correct
5 Correct 31 ms 9280 KB Output is correct
6 Correct 56 ms 10344 KB Output is correct
7 Correct 34 ms 12948 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 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 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 2 ms 2900 KB Output is correct
12 Correct 2 ms 2900 KB Output is correct
13 Execution timed out 2086 ms 23400 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 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 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1197 ms 8560 KB Output is correct
11 Correct 402 ms 13172 KB Output is correct
12 Execution timed out 2083 ms 10196 KB Time limit exceeded
13 Halted 0 ms 0 KB -