Submission #1042485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042485		pawned	Friend (IOI14_friend)	C++17	100 / 100	15 ms	3516 KiB

friend

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "friend.h"

int findSample(int N, int c[], int hs[], int pr[]) {
	vi x1(N, 0);	// max sum for choose
	for (int i = 0; i < N; i++) {
		x1[i] = c[i];
	}
	vi x2(N, 0);	// max sum for not choose
	for (int i = N - 1; i >= 1; i--) {
		if (pr[i] == 2) {
			int a = max(x1[hs[i]] + x2[i], x1[i] + x2[hs[i]]);
			int b = x2[hs[i]] + x2[i];
			x1[hs[i]] = a; x2[hs[i]] = b;
		}
		else if (pr[i] == 1) {
			int a = max(x1[hs[i]] + x1[i], max(x1[hs[i]] + x2[i], x1[i] + x2[hs[i]]));
			int b = x2[hs[i]] + x2[i];
			x1[hs[i]] = a; x2[hs[i]] = b;
		}
		else if (pr[i] == 0) {
			int a = x1[hs[i]] + x2[i];
			int b = max(x1[i] + x2[hs[i]], x2[i] + x2[hs[i]]);
			x1[hs[i]] = a; x2[hs[i]] = b;
		}
	}
/*	cout<<"x1: ";
	for (int x : x1)
		cout<<x<<" ";
	cout<<endl;
	cout<<"x2: ";
	for (int x : x2)
		cout<<x<<" ";
	cout<<endl;*/
	return max(x1[0], x2[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