IOI 2014. day 2

friend.cpp

#include "friend.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100100;

int take[MAXN], dont[MAXN];

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[])
{
	int i;
	
	for (i = 0; i < n; ++i)
	{
		take[i] = confidence[i];
		dont[i] = 0;
	}
	
	for (i = n - 1; i > 0; --i) switch (protocol[i])
	{
	case 0:
		take[host[i]] += dont[i];
		dont[host[i]] += max(take[i], dont[i]);
		break;
	case 1:
		take[host[i]] = max(take[host[i]] + take[i], max(take[host[i]] + dont[i], dont[host[i]] + take[i]));
		dont[host[i]] += dont[i];
		break;
	case 2:
		take[host[i]] = max(take[host[i]] + dont[i], dont[host[i]] + take[i]);
		dont[host[i]] += dont[i];
		break;
	}
	
	return max(take[0], dont[0]);
}