Submission #1219577


Source Code Expand

#include <iostream>
#include <bitset>
#include <vector>
#include <set>

typedef std::bitset<100> JewelFlags;
typedef std::bitset<100> VisitedFlags;
typedef std::vector<std::bitset<100>> EdgeTable;

std::pair<int, bool> 
search(
  const EdgeTable &edge, 
  const JewelFlags &jewel, 
  unsigned node, 
  const VisitedFlags &visited
)
{
  int sum = 0;
  
  for (unsigned next = 0; next < edge.size(); ++next) {
    if (!visited[next] && edge[node][next]) {
      VisitedFlags flag(visited);
      flag[next] = true;
      
      std::pair<int, bool> ret = search(edge, jewel, next, flag);
      if (ret.second) sum += ret.first + 2;
    }
  }
  
  return std::pair<int, bool>(sum , jewel[node] || sum > 0);
}

int search(
  const EdgeTable &edge, 
  const JewelFlags &jewel, 
  unsigned node
)
{
  VisitedFlags init_flag;
  init_flag[node] = true;

  std::pair<int, bool> ret = search(edge, jewel, node, init_flag);

  return ret.first;
}

int main()
{
  unsigned N, x;
  std::cin >> N >> x;
  
  std::vector<unsigned> h(N);
  for (unsigned n = 0; n < N; ++n) {
    std::cin >> h[n];
  }
  
  JewelFlags jewel;
  for (unsigned n = 0; n < N; ++n) {
    if(h[n] > 0) jewel[n] = true;
  }
  
  EdgeTable edge(N);
  for (unsigned n = 0; n < N - 1; ++n) {
    unsigned a, b;
    std::cin >> a >> b;
    
    edge[b - 1][a - 1] = true;
    edge[a - 1][b - 1] = true;
  }
  
  std::cout << search(edge, jewel, x - 1) << std::endl;
  
  return 0;
}

Submission Info

Submission Time
Task B - ツリーグラフ
User material
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1510 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 20
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_line01.txt, subtask1_line02.txt, subtask1_line03.txt, subtask1_line04.txt, subtask1_line05.txt, subtask1_line06.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask1_line01.txt AC 1 ms 256 KB
subtask1_line02.txt AC 1 ms 256 KB
subtask1_line03.txt AC 1 ms 256 KB
subtask1_line04.txt AC 1 ms 256 KB
subtask1_line05.txt AC 1 ms 256 KB
subtask1_line06.txt AC 1 ms 256 KB
subtask1_random01.txt AC 1 ms 256 KB
subtask1_random02.txt AC 1 ms 256 KB
subtask1_random03.txt AC 1 ms 256 KB
subtask1_random04.txt AC 1 ms 256 KB
subtask1_random05.txt AC 1 ms 256 KB
subtask1_random06.txt AC 1 ms 256 KB
subtask1_random07.txt AC 1 ms 256 KB
subtask1_random08.txt AC 1 ms 256 KB
subtask1_special01.txt AC 1 ms 256 KB
subtask1_special02.txt AC 1 ms 256 KB
subtask1_special03.txt AC 1 ms 256 KB
subtask1_special04.txt AC 1 ms 256 KB