Submission #257582

#	Time	Username	Problem	Language	Result	Execution time	Memory
257582		Berted	Friend (IOI14_friend)	C++14	100 / 100	40 ms	3448 KiB

friend

#include "friend.h"
#include <tuple>
#include <algorithm>
#include <utility>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

/*
	Solve from last query
	We can maintain (A, B) for each node where
	A is MWIS with current node used
	B is MWIS without current node used
	By running backwrds, we "merge" two nodes into one.
*/

pii ar[100001];

int findSample(int n, int confidence[], int host[], int protocol[]){
	for (int i = 0; i < n; i++) {ar[i].fst = confidence[i];}
	for (int i = n - 1; i; i--)
	{
		if (protocol[i] == 0) ar[host[i]] = make_pair(ar[host[i]].fst + ar[i].snd, ar[host[i]].snd + max(ar[i].fst, ar[i].snd));
		else if (protocol[i] == 1) ar[host[i]] = make_pair(max({ar[host[i]].fst + ar[i].fst, ar[host[i]].fst + ar[i].snd, ar[host[i]].snd + ar[i].fst}), ar[host[i]].snd + ar[i].snd);
		else ar[host[i]] = make_pair(max(ar[host[i]].fst + ar[i].snd, ar[i].fst + ar[host[i]].snd), ar[host[i]].snd + ar[i].snd);
	}
	return max(ar[0].fst, ar[0].snd);
}

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31