Submission #1284655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284655		LucaLucaM	친구 (IOI14_friend)	C++20	35 / 100	21 ms	7048 KiB

friend

#include "friend.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

// Find out best sample
int findSample(int n, int a[], int parent[], int type[]) {
  std::vector<std::vector<int>> dp(n, std::vector<int>(2, 0));

  for (int i = 0; i < n; i++) {
    dp[i][1] = a[i];
  }

  for (int v = n - 1; v > 0; v--) { 
    int u = parent[v];
    if (type[v] == 0) {
      dp[u][0] += std::max(dp[v][0], dp[v][1]);
      dp[u][1] += dp[v][0];
    } else if (type[v] == 1) {
      dp[u][0] += dp[v][0];
      dp[u][1] = std::max({dp[u][1] + dp[v][1], dp[u][1] + dp[v][0], dp[u][0] + dp[v][1]});
    } else {
      dp[u][0] += dp[v][0];
      dp[u][1] = std::max(dp[u][1] + dp[v][0], dp[u][0] + dp[v][1]);
    }
  }

  return std::max(dp[0][0], dp[0][1]);
}

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