#include "friend.h" #include <vector> using namespace std; int No[100'000]; // Find out best sample int findSample(int n,int Yes[],int host[],int protocol[]) { for(int i = n-1; i >= 1; i--) { if(protocol[i] == 0) //I am your friend { //yes i, yes host[i] //no i, yes host[i] Yes[ host[i] ] += No[i]; //yes i, no host[i] //no i, no host[i] No[ host[i] ] += max(Yes[i], No[i]); } else if(protocol[i] == 1) //My friends are your friends { //yes i, yes host[i] //no i, yes host[i] //yes i, no host[i] Yes[ host[i] ] = max(Yes[ host[i] ], No[ host[i] ]) + max(Yes[i], No[i]); // Yes[ host[i] ] = Yes[ host[i] ] + max(Yes[i], No[i]); //no i, no host[i] No[ host[i] ] += No[i]; } else //We are your friends { //yes i, yes host[i] //no i, yes host[i] //yes i, no host[i] Yes[ host[i] ] = max(Yes[ host[i] ] + No[i], No[ host[i] ] + Yes[i]); //no i, no host[i] No[ host[i] ] += No[i]; } } return max(Yes[0], No[0]); }