oj.uz

답안 #333848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333848 2020-12-07T23:47:40 Z limabeans 바이오칩 (IZhO12_biochips) C++17
0 / 100
 49 ms 16236 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+10;


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) {

    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<=cloc; i++) {
	for (int j=0; j<=m; 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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5612 KB Output is correct
4 Runtime error 49 ms 16236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -