oj.uz

Submission #333852

# Submission time Handle Problem Language Result Execution time Memory
333852 2020-12-07T23:52:09 Z limabeans Biochips (IZhO12_biochips) C++17
100 / 100
 1055 ms 411756 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl











const int maxn = 2e5 + 100;


int n,m;
vector<int> g[maxn];
int a[maxn];

int cloc = 0;
int tin[maxn];
int arr[maxn];
int tout[maxn];

void dfs(int at, int p) {

    assert(cloc<maxn);
    
    arr[cloc] = at;
    tin[at] = cloc;
    cloc++;
    
    for (int to: g[at]) {
	if (to == p) continue;
	dfs(to, at);
    }

    tout[at] = cloc;
}


void setmax(int &x, int y) {
    x = max(x, y);
}

int dp[512][maxn];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    int r=-1;
    for (int i=1; i<=n; i++) {
	int p;
	cin>>p;
	if (p==0) {
	    r=i;
	} else {
	    g[p].push_back(i);
	}
	cin>>a[i];
    }


    dfs(r,-1);




    for (int i=0; i<512; i++) {
	for (int j=0; j<maxn; j++) {
	    dp[i][j] = -1e9;
	}
    }

    
    dp[0][0] = 0;


    for (int j=0; j<=m; j++) {
	for (int i=0; i<cloc; i++) {

	    int ptr = tout[arr[i]];
	    if (j<m) {
		setmax(dp[j+1][ptr], dp[j][i]+a[arr[i]]);
	    }
	    setmax(dp[j][i+1], dp[j][i]);
	}
    }

    cout<<dp[m][cloc]<<endl;
    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 405996 KB Output is correct
2 Correct 256 ms 405996 KB Output is correct
3 Correct 249 ms 405996 KB Output is correct
4 Correct 257 ms 406380 KB Output is correct
5 Correct 281 ms 406496 KB Output is correct
6 Correct 261 ms 406380 KB Output is correct
7 Correct 1055 ms 411012 KB Output is correct
8 Correct 1045 ms 410996 KB Output is correct
9 Correct 776 ms 411244 KB Output is correct
10 Correct 989 ms 411756 KB Output is correct