oj.uz

Submission #918489

# Submission time Handle Problem Language Result Execution time Memory
918489 2024-01-29T23:40:15 Z contest_alt Friend (IOI14_friend) C++17
35 / 100
 1 ms 600 KB 
#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[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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Incorrect 0 ms 432 KB Output isn't correct
8 Halted 0 ms 0 KB -