Submission #1112031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112031		Tsagana	Biochips (IZhO12_biochips)	C++14	100 / 100	348 ms	399356 KiB

biochips

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

vector<int> adj[200001];
int dp[200001][501];
int a[200001];
int b[200001];
int n, m, cnt = 0;

void dfs(int v){
	b[v] = cnt;
	for (auto i: adj[v]) dfs(i);
	for (int i = 1; i <= m; i++) dp[cnt+1][i] = max(dp[cnt][i], dp[b[v]][i - 1] + a[v]);
	cnt++;
}

void solve () {
	cin >> n >> m;
	int r;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x >> a[i];
		if (!x) r = i;
		else adj[x].pb(i);
	}
	for (int i = 1; i <= m; i++) dp[0][i] = -2e5;
	dfs(r);
	cout << dp[n][m];
}
int main() {IOS solve(); return 0;}

Compilation message (stderr)

biochips.cpp: In function 'void solve()':
biochips.cpp:39:5: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |  dfs(r);
      |  ~~~^~~

• Subtask 1: 100 / 100