Submission #287678


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>

using namespace std;

int n,x;
int hs[101];
int ls[101];
int vs[101];
int ps[101];


int main(){
  cin >> n >> x;
  for(int i=1;i<=n;++i){
    cin >> hs[i];
  }
  multimap<int,int> tree;
  for(int i=1;i<n;++i){
    int a,b;
    cin >> a >> b;
    tree.insert(make_pair(a,b));
    tree.insert(make_pair(b,a));
  }

  int node = x;
  queue<int> q;

  q.push(x);
  vs[x] = 1;
  while (!q.empty()){
    int node = q.front();
    if(tree.count(node)==1)
      ls[node] = 1;
    auto search = tree.equal_range(node);
    for(auto i=search.first;i!=search.second;++i){
      if(!vs[i->second]) q.push(i->second);
    }
    vs[node] = 1;
    q.pop();
  }

  queue<int> qq;
  for(int i=0;i<=n;++i){
    if(ls[i]) {
      qq.push(i);
    }
  }

  while(qq.size()){
    int node = qq.front();
    if(!hs[node]){
      ps[node] = 1;
      auto search = tree.equal_range(node);
      for(auto i=search.first;i!=search.second;++i){
        if(!ps[node])
          qq.push(i->second);
      }
    }
    qq.pop();
  }

  int ans = n-1;
  for(int i=1;i<=n;++i)
    if(ps[i]) --ans;

  cout << (max(ans,0))*2 << endl;

}

Submission Info

Submission Time
Task B - ツリーグラフ
User yasuyuky
Language C++11 (GCC 4.8.1)
Score 0
Code Size 1261 Byte
Status WA
Exec Time 29 ms
Memory 932 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 10
WA × 10
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 29 ms 800 KB
subtask0_sample_02.txt AC 20 ms 800 KB
subtask1_line01.txt AC 23 ms 796 KB
subtask1_line02.txt WA 21 ms 928 KB
subtask1_line03.txt WA 23 ms 932 KB
subtask1_line04.txt WA 23 ms 924 KB
subtask1_line05.txt AC 23 ms 748 KB
subtask1_line06.txt WA 23 ms 924 KB
subtask1_random01.txt WA 22 ms 800 KB
subtask1_random02.txt AC 23 ms 800 KB
subtask1_random03.txt WA 22 ms 800 KB
subtask1_random04.txt WA 22 ms 924 KB
subtask1_random05.txt WA 23 ms 928 KB
subtask1_random06.txt AC 24 ms 924 KB
subtask1_random07.txt WA 22 ms 800 KB
subtask1_random08.txt WA 22 ms 800 KB
subtask1_special01.txt AC 23 ms 796 KB
subtask1_special02.txt AC 22 ms 924 KB
subtask1_special03.txt AC 22 ms 928 KB
subtask1_special04.txt AC 23 ms 804 KB