Submission #750609


Source Code Expand

Copy
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int search(int cur, int h[], vector<int> edges[], int min_costs[], int parent = -1) {
  int &cost = min_costs[cur];
  if (cost < 0) {
    cost = 0;
    for (size_t ei = 0; ei < edges[cur].size(); ++ei) {
      int next = edges[cur][ei];
      if (next != parent) {
        int child_cost = search(next, h, edges, min_costs, cur);
        if (child_cost > 0 or h[next]) {
          cost += child_cost + 2;
        }
      }
    }
  }
  return cost;
}

int main() {
  int n, x, a, b;
  int h[100], min_costs[100];
  vector<int> edges[100];
  cin >> n >> x;
  for (int ni = 0; ni < n; ++ni) {
    cin >> h[ni];
  }
  for (int ni = 0; ni < n - 1; ++ni) {
    cin >> a >> b;
    edges[a - 1].push_back(b - 1);
    edges[b - 1].push_back(a - 1);
  }
  fill(min_costs, min_costs + n, -1);
  cout << search(x - 1, h, edges, min_costs) << endl;
  return 0;
}

Submission Info

Submission Time
Task B - ツリーグラフ
User saltcandy123
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1011 Byte
Status AC
Exec Time 27 ms
Memory 928 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 24 ms 796 KB
subtask0_sample_02.txt AC 25 ms 672 KB
subtask1_line01.txt AC 26 ms 800 KB
subtask1_line02.txt AC 23 ms 800 KB
subtask1_line03.txt AC 25 ms 916 KB
subtask1_line04.txt AC 25 ms 800 KB
subtask1_line05.txt AC 26 ms 868 KB
subtask1_line06.txt AC 24 ms 736 KB
subtask1_random01.txt AC 26 ms 736 KB
subtask1_random02.txt AC 25 ms 928 KB
subtask1_random03.txt AC 24 ms 800 KB
subtask1_random04.txt AC 25 ms 800 KB
subtask1_random05.txt AC 25 ms 920 KB
subtask1_random06.txt AC 27 ms 768 KB
subtask1_random07.txt AC 25 ms 924 KB
subtask1_random08.txt AC 23 ms 800 KB
subtask1_special01.txt AC 25 ms 796 KB
subtask1_special02.txt AC 25 ms 716 KB
subtask1_special03.txt AC 23 ms 924 KB
subtask1_special04.txt AC 23 ms 800 KB