oj.uz

답안 #954358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954358 2024-03-27T16:37:24 Z starchan 바이오칩 (IZhO12_biochips) C++17
30 / 100
 443 ms 402064 KB 
#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
const int MX = 2e5+5, SMX = 5e2+2;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<int> adj[MX];
int dp[MX][SMX];
int chungus[SMX];//initialised with zero.
vector<int> w;
vector<int> euler;
int timer;
vector<int> tin;
int m;
vector<int> tout;
void dfs(int u)
{
	euler.pb(u);
	tin[u] = timer++;
	for(int v: adj[u])
		dfs(v);
	for(int i = 1; i <= m; i++)
		dp[tin[u]][i] = max(((tin[u] > 0) ? dp[tin[u]-1][i] : 0), w[u] + chungus[i-1]);
	for(int i = 1; i <= m; i++)
		chungus[i] = max(chungus[i], dp[tin[u]][i]);
	return;
}
signed main()
{
	fast();
	//freopen("d.in", "r", stdin);
	//freopen("d.out", "w", stdout);
	int n;
	cin >> n >> m;
	w.resize(n+1);
	tin.resize(n+1);
	int root = -1;
	for(int i = 1; i <= n; i++)
	{
		int x; cin >> x >> w[i];
		if(x)
			adj[x].pb(i);
		else
			root = i;
	}
	dfs(root);
	cout << dp[n-1][m] << "\n";
	return 0;
}

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 5980 KB Output isn't correct
2 Correct 2 ms 5980 KB Output is correct
3 Incorrect 2 ms 8028 KB Output isn't correct
4 Incorrect 10 ms 23716 KB Output isn't correct
5 Incorrect 10 ms 26972 KB Output isn't correct
6 Incorrect 11 ms 26972 KB Output isn't correct
7 Incorrect 245 ms 300108 KB Output isn't correct
8 Correct 254 ms 300044 KB Output is correct
9 Correct 329 ms 364180 KB Output is correct
10 Incorrect 443 ms 402064 KB Output isn't correct