Submission #385939

#	Time	Username	Problem	Language	Result	Execution time	Memory
385939		alireza_kaviani	Friend (IOI14_friend)	C++11	58 / 100	34 ms	3436 KiB

friend

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

typedef pair<int, int> pii;

#define X			first
#define Y			second
#define all(x)		(x).begin() , (x).end()
#define SZ(x)		int(x.size())

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

int dp[2][MAXN];

int findSample(int n,int confidence[],int host[],int protocol[]){
	for(int i = 0 ; i < n ; i++){
		dp[1][i] = confidence[i];
	}
	for(int i = n - 1 ; i > 0 ; i--){
		if(protocol[i] == 0){
			dp[1][host[i]] += dp[0][i];
			dp[0][host[i]] += max(dp[0][i] , dp[1][i]);
		}
		if(protocol[i] == 1){
			dp[1][host[i]] = max({dp[0][host[i]] + dp[1][i] , dp[1][host[i]] + dp[1][i] , dp[1][host[i]] + dp[0][i]});
			dp[0][host[i]] += dp[0][i];
		}
		if(protocol[i] == 2){
			dp[0][host[i]] = max(dp[0][host[i]] , dp[0][i]);
			dp[1][host[i]] = max(dp[1][host[i]] , dp[1][i]);
		}
	}
	return max(dp[0][0] , dp[1][0]);
}

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