oj.uz

Submission #659883

# Submission time Handle Problem Language Result Execution time Memory
659883 2022-11-19T15:57:04 Z 600Mihnea Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 23436 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];

void bu(int a) {
  ord[++top] = a;
  low[a] = top;
  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) {
  vector<pair<int, ll>> sol;
  for (int j = low[v]; j <= high[v]; j++) {
    if (int i = type[ord[j]]) {
   ///
    }
  }
  for (int i = 1; i <= k; i++) {
    if (dp[i] != dp[i - 1]) {
      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 'std::vector<std::pair<int, long long int> > get_and_clr_dp(int)':
magictree.cpp:42:13: warning: unused variable 'i' [-Wunused-variable]
   42 |     if (int i = type[ord[j]]) {
      |             ^
magictree.cpp: In function 'int main()':
magictree.cpp:100:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 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 2066 ms 8352 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 2900 KB Output is correct
2 Correct 3 ms 2872 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Execution timed out 2071 ms 23436 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7392 KB Output is correct
2 Correct 52 ms 7396 KB Output is correct
3 Correct 85 ms 13260 KB Output is correct
4 Correct 41 ms 10916 KB Output is correct
5 Correct 46 ms 19788 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 63 ms 7380 KB Output is correct
11 Correct 56 ms 7376 KB Output is correct
12 Correct 55 ms 13288 KB Output is correct
13 Correct 40 ms 10908 KB Output is correct
14 Correct 46 ms 19796 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3668 KB Output is correct
2 Correct 69 ms 7480 KB Output is correct
3 Correct 76 ms 7452 KB Output is correct
4 Correct 92 ms 7472 KB Output is correct
5 Correct 98 ms 9224 KB Output is correct
6 Correct 83 ms 10316 KB Output is correct
7 Correct 46 ms 12936 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 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 3 ms 2872 KB Output is correct
12 Correct 2 ms 2900 KB Output is correct
13 Execution timed out 2071 ms 23436 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Execution timed out 2066 ms 8352 KB Time limit exceeded
11 Halted 0 ms 0 KB -