Submission #58889

#	Time	Username	Problem	Language	Result	Execution time	Memory
58889		kingpig9	Friend (IOI14_friend)	C++11	100 / 100	55 ms	5192 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 100010;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int cho[MAXN], ncho[MAXN];	//choose, not choose

int findSample (int N, int C[], int H[], int type[]) {
	for (int i = 0; i < N; i++) {
		cho[i] = C[i];
	}

	//ok let's do this
	for (int y = N - 1; y >= 1; y--) {
		int x = H[y];
		if (type[y] == 0) {
			//IAmYourFriend
			tie(cho[x], ncho[x]) = pii(cho[x] + ncho[y], max(ncho[x] + cho[y], ncho[x] + ncho[y]));
		} else if (type[y] == 1) {
			//MyFriendsAreYourFriends
			//we can just combine them
			tie(cho[x], ncho[x]) = pii(max({cho[x] + cho[y], cho[x] + ncho[y], ncho[x] + cho[y]}), ncho[x] + ncho[y]);
		} else if (type[y] == 2) {
			//WeAreYourFriends
			tie(cho[x], ncho[x]) = pii(max(cho[x] + ncho[y], ncho[x] + cho[y]), ncho[x] + ncho[y]);
		} else {
			assert(!"Bad type");
		}
	}
	return max(cho[0], ncho[0]);
}

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