Submission #286822


Source Code Expand

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int lli;
typedef pair<int, int> Pii;

vector<int> edge[100];
int n, x;
int h[100];
bool flg[100];

int ans;

bool rec(int curr, int prev) {
  bool f = h[curr];

  rep(i, edge[curr].size()) if (edge[curr][i] != prev) {
    f |= rec(edge[curr][i], curr);
  }

  return flg[curr] = f;
}

void solve(int curr, int prev) {
  rep(i, edge[curr].size()) if (edge[curr][i] != prev && flg[edge[curr][i]]){
    ans += 2;
    solve(edge[curr][i], curr);
  }
}

int main() {
  // ios_base::sync_with_stdio(false);
  cin >> n >> x;
  x--;
  rep(i, n) cin >> h[i];
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edge[a].pb(b);
    edge[b].pb(a);
  }

  memset(flg, false, sizeof(flg));

  rec(x, -1);

  ans = 0;
  solve(x, -1);

  cout << ans << endl;
  
  return 0;
}

Submission Info

Submission Time
Task B - ツリーグラフ
User purple928
Language C++ (G++ 4.6.4)
Score 100
Code Size 1153 Byte
Status AC
Exec Time 24 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 21 ms 804 KB
subtask0_sample_02.txt AC 22 ms 800 KB
subtask1_line01.txt AC 21 ms 800 KB
subtask1_line02.txt AC 23 ms 928 KB
subtask1_line03.txt AC 22 ms 924 KB
subtask1_line04.txt AC 21 ms 920 KB
subtask1_line05.txt AC 23 ms 672 KB
subtask1_line06.txt AC 23 ms 804 KB
subtask1_random01.txt AC 24 ms 776 KB
subtask1_random02.txt AC 23 ms 920 KB
subtask1_random03.txt AC 22 ms 804 KB
subtask1_random04.txt AC 21 ms 772 KB
subtask1_random05.txt AC 23 ms 796 KB
subtask1_random06.txt AC 23 ms 740 KB
subtask1_random07.txt AC 22 ms 920 KB
subtask1_random08.txt AC 23 ms 796 KB
subtask1_special01.txt AC 21 ms 800 KB
subtask1_special02.txt AC 23 ms 800 KB
subtask1_special03.txt AC 22 ms 800 KB
subtask1_special04.txt AC 22 ms 852 KB