oj.uz

Submission #1112031

# Submission time Handle Problem Language Result Execution time Memory
1112031 2024-11-13T14:27:53 Z Tsagana Biochips (IZhO12_biochips) C++14
100 / 100
 348 ms 399356 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5200 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 5200 KB Output is correct
4 Correct 15 ms 22764 KB Output is correct
5 Correct 16 ms 24904 KB Output is correct
6 Correct 17 ms 24824 KB Output is correct
7 Correct 229 ms 298072 KB Output is correct
8 Correct 264 ms 298056 KB Output is correct
9 Correct 312 ms 361912 KB Output is correct
10 Correct 348 ms 399356 KB Output is correct