답안 #954359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954359 2024-03-27T16:42:45 Z starchan 바이오칩 (IZhO12_biochips) C++17
30 / 100
482 ms 400544 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++)
			chungus[i] = max(chungus[i], dp[tin[v]][i]);
	}
	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]);
	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;
}	
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5980 KB Output isn't correct
2 Correct 2 ms 5980 KB Output is correct
3 Incorrect 3 ms 8028 KB Output isn't correct
4 Incorrect 11 ms 23732 KB Output isn't correct
5 Incorrect 11 ms 26972 KB Output isn't correct
6 Incorrect 10 ms 26968 KB Output isn't correct
7 Incorrect 278 ms 298768 KB Output isn't correct
8 Correct 258 ms 298652 KB Output is correct
9 Correct 372 ms 362940 KB Output is correct
10 Incorrect 482 ms 400544 KB Output isn't correct