Submission #519545

#	Time	Username	Problem	Language	Result	Execution time	Memory
519545		NDT	Biochips (IZhO12_biochips)	C++14	100 / 100	428 ms	411716 KiB

biochips

#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 / 100