Submission #918490

#	Time	Username	Problem	Language	Result	Execution time	Memory
918490		contest_alt	Friend (IOI14_friend)	C++17	100 / 100	20 ms	3452 KiB

friend

#include "friend.h"

int min( int a, int b ) { return a < b ? a : b; }
int max( int a, int b ) { return a > b ? a : b; }

int findSample( int n, int confidence[], int host[], int protocol[] ) {
  int *choose = new int[n];
  int *not_choose = new int[n];

  for( int i = 0 ; i < n ; i++ ){
    choose[i] = confidence[i];
    not_choose[i] = 0;
  }

  for( int i = n - 1 ; i > 0 ; i-- ){
    // we merge the two nodes (i, host[i]) into one single node
    // this explains the wierd asignment of sums

    if( protocol[i] == 0 ){
      int new_choose = choose[host[i]] + not_choose[i]; // choose host[i] and not i
      int new_not_choose = not_choose[host[i]] + max( choose[i], not_choose[i] ); // choose i and not host[i] or choose none

      choose[host[i]] = new_choose;
      not_choose[host[i]] = new_not_choose;

    }else if( protocol[i] == 1 ){
      // if we choose any of the two nodes that means we choose the merged node
      int new_choose = max( choose[i] + choose[host[i]], max( choose[i] + not_choose[host[i]], not_choose[i] + choose[host[i]] ) );
      int new_not_choose = not_choose[host[i]] + not_choose[i];

      choose[host[i]] = new_choose;
      not_choose[host[i]] = new_not_choose;
      
    }else{
      int new_choose = max( choose[host[i]] + not_choose[i], not_choose[host[i]] + choose[i] );
      int new_not_choose = not_choose[i] + not_choose[host[i]];

      choose[host[i]] = new_choose;
      not_choose[host[i]] = new_not_choose;
    }
  }

  int ret = max( choose[0], not_choose[0] );

  delete []choose;
  delete []not_choose;

  return ret;
}

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