제출 #1284577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284577		LucaLucaM	친구 (IOI14_friend)	C++20	35 / 100	1 ms	580 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>> g(n);
  std::vector<int> who(n);
  std::vector<int> hater(n, 0);
  std::vector<int> chill(n, 0);
  who[0] = 0;
  chill[0] = a[0];

  for (int i = 1; i < n; i++) {
    if (type[i] == 0) { // I am your friend  
      g[who[parent[i]]].push_back(i);
      who[i] = i;
      chill[who[i]] += a[i];
    } else if (type[i] == 1) { // My friend are your friends
      who[i] = who[parent[i]];
      chill[who[i]] += a[i];
    } else { // We are your friends
      who[i] = who[parent[i]];
      hater[who[i]] = std::max(hater[who[i]], a[i]);
    }
  }

  std::vector<std::vector<int>> dp(n, std::vector<int>(2, 0));

  auto dfs = [&](auto &&self, int u) -> void {
    dp[u][0] = 0;
    dp[u][1] = std::max(chill[u], hater[u]);
    
    for (int v : g[u]) {
      self(self, v);
      dp[u][1] += dp[v][0];
      dp[u][0] += std::max(dp[v][0], dp[v][1]);
    }
  };

  dfs(dfs, 0);
  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