oj.uz

Submission #519545

# Submission time Handle Problem Language Result Execution time Memory
519545 2022-01-26T15:54:10 Z NDT Biochips (IZhO12_biochips) C++14
100 / 100
 428 ms 411716 KB 
#include <bits/stdc++.h>

using namespace std;
#define task "biochip"
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define le(id) (id << 1)
#define ri(id) (id << 1 | 1)
#define pb push_back
#define pf push_front
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef double db;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int N = 2e5 + 2;
const int M = 5e2 + 2;
const int inf = 1e8;
int in[N], n, m, DFSTime, out[N], f[N][M], w[N], root;
vi last[N], adj[N];

void DFS(int u, int pr) {
  in[u] = ++DFSTime;
  for (int v : adj[u]) {
    if (v == pr) continue;
    DFS(v, u);
  }
  out[u] = DFSTime;
  last[DFSTime].pb(u);
}

int main()
{
  ios_base::sync_with_stdio(false); cin.tie(0);
//  freopen(task".inp", "r", stdin);
//  freopen(task".out", "w", stdout);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    int j;
    cin >> j >> w[i];
    if (j != 0) {
      adj[j].pb(i);
//      adj[i].pb(j);
    }
    else root = i;
  }
  DFS(root, root);
  for (int j = 1; j <= m; ++j) f[0][j] = -inf;
  f[0][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      f[i][j] = f[i - 1][j];
      for (int x : last[i]) {
        f[i][j] = max(f[i][j], f[in[x] - 1][j - 1] + w[x]);
      }
    }
  }
  cout << f[n][m] << '\n';
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9716 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 17 ms 27600 KB Output is correct
5 Correct 20 ms 29796 KB Output is correct
6 Correct 20 ms 29872 KB Output is correct
7 Correct 302 ms 308312 KB Output is correct
8 Correct 270 ms 308208 KB Output is correct
9 Correct 341 ms 373420 KB Output is correct
10 Correct 428 ms 411716 KB Output is correct