Submission #92434

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92434	2019-01-02T20:43:45 Z	luciocf	Biochips (IZhO12_biochips)	C++14	0 / 100	350 ms	405468 KB

biochips

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;

const int maxm = 5e2+10;

const int inf = 1e9+10;

typedef pair<int, int> pii;

struct Leaf
{
	int l, r, v, ind;
} f[maxn], aux[maxn];

int n, m, l, num[maxn], root;

int nxt[2][maxn], dp[maxn][maxm];

vector<int> grafo[maxn];


void dfs(int u, int p)
{
	if (grafo[u].size() == 1 && u != root)
	{
		f[u] = {++l, ++l, num[u], 0};
		return;
	}

	for (auto v: grafo[u])
		if (v != p)
			dfs(v, u);	

	f[u].v = num[u], f[u].l = inf;
	for (auto v: grafo[u])
	{
		if (v == p) continue;
		f[u].l = min(f[u].l, f[v].l);
		f[u].r = max(f[u].r, f[v].r);
	}
}

bool comp(Leaf a, Leaf b)
{
	if (a.r == b.r) return a.l < b.l;
	return a.r < b.r;
}

bool comp2(Leaf a, Leaf b)
{
	if (a.l == b.l) return a.r < b.r;
	return a.l < b.l;
}

int solve(int pos, int x)
{
	if (pos == n+1 && x == m+1) return 0;
	if (pos == n+1) return -inf;
	if (dp[pos][x] != -1) return dp[pos][x];

	int caso1 = solve(pos+1, x);
	int caso2 = aux[pos].v+solve(nxt[1][pos], x+1);

	return dp[pos][x] = max(caso1, caso2);
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		int p;
		cin >> p >> num[i];

		if (p)
		{
			grafo[i].push_back(p);
			grafo[p].push_back(i);
		}

		if (!p) root = i;
	}

	if (n == 1)
	{
		cout << num[1] << "\n";
		return 0;
	}

	dfs(root, 0);

	sort(f+1, f+n+1, comp);

	for (int i = 1; i <= n; i++)
	{
		aux[i] = f[i];
		aux[i].ind = i;
	}

	sort(aux+1, aux+n+1, comp2);

	for (int i = 1; i <= n; i++)
		f[aux[i].ind].ind = i;

	int ptr = n;
	for (int i = n; i >= 1; i--)
	{
		if (f[i].r >= aux[ptr].l)
		{
			nxt[0][i] = n+1;
			continue;
		}

		while (f[i].r < aux[ptr-1].l) ptr--;

		nxt[0][i] = aux[ptr].ind;
	}

	for (int i = 1; i <= n; i++)
	{
		nxt[1][f[i].ind] = f[nxt[0][i]].ind;
		if (nxt[0][i] == n+1) nxt[1][f[i].ind] = n+1;
	}

	memset(dp, -1, sizeof dp);
	cout << solve(1, 1) << "\n"; 
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	279 ms	404532 KB	Output is correct
2	Correct	280 ms	404312 KB	Output is correct
3	Correct	275 ms	404344 KB	Output is correct
4	Incorrect	350 ms	405468 KB	Output isn't correct
5	Halted	0 ms	0 KB	-