Submission #126877

#	Time	Username	Problem	Language	Result	Execution time	Memory
126877		ekrem	Friend (IOI14_friend)	C++98	100 / 100	42 ms	4344 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
 
int n, al[N], alma[N], yal[N], yalma[N];
 
int findSample(int n,int c[],int h[],int p[]){
	for(int i = 0; i < n; i++){
		al[i] = c[i];
		alma[i] = 0;
	}
	for(int y = n - 1; y >= 1; y--){
		int x = h[y];
		if(p[y] == 2){
			yalma[x] = alma[x] + alma[y];
			yal[x] = max(al[y] + alma[x], alma[y] + al[x]);
		} else if(p[y] == 1){
			yalma[x] = alma[x] + alma[y];
			yal[x] = max(max(al[x] + alma[y], alma[x] + al[y]), al[x] + al[y]);
		} else{
			yalma[x] = alma[x] + max(al[y], alma[y]);
			yal[x] = al[x] + alma[y];
		}
		swap(yal[x], al[x]);
		swap(yalma[x], alma[x]);
	}
	return max(al[0], alma[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