Contest Duration: - (local time) (90 minutes) Back to Home

Submission #287600

Source Code Expand

Copy
```#include <iostream>
#include <stdio.h>
#include <istream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cstring>

using namespace std;

typedef long long int ll;

const int MAX_N = 100;
int N;

vector<int> G[MAX_N];
bool used[MAX_N];
bool h[MAX_N];
bool transh[MAX_N];

// contain?
bool dfs(int v) {
used[v] = true;

bool ans = h[v];
for (int i = 0; i < G[v].size(); i++) {
if (!used[G[v][i]]) {
ans |= dfs(G[v][i]);
}
}
transh[v] = ans;
return ans;
}

int dfs2(int v) {
used[v] = true;

int ans = 0;
for (int i = 0; i < G[v].size(); i++) {
int to = G[v][i];
if (!used[to] && transh[to]) {
ans += 1 + dfs2(to);
}
}

return ans;
}

int main(int argc, const char * argv[])
{
int _x;
cin >> N >> _x;
const int x = _x - 1;

int hcount = 0;
for (int i = 0; i < N; i++) {
int b;
cin >> b;
h[i] = (b == 1);
if (b == 1) { hcount++; };
}

for (int i = 0; i < N-1; i++) {
int a, b;
cin >> a >> b;
a--; b--;
G[a].push_back(b);
G[b].push_back(a);
}

memset(used, 0, sizeof(used));
dfs(x);

//    for (int i = 0; i < N; i++) {
//        cout << transh[i] << endl;
//    }
//    cout << endl;

memset(used, 0, sizeof(used));
int ret = dfs2(x);

cout << ret * 2 << endl;
}

```

#### Submission Info

Submission Time 2014-11-29 23:14:41+0900 B - ツリーグラフ nida_001 C++11 (GCC 4.8.1) 100 1718 Byte AC 24 ms 924 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
 AC × 2
 AC × 20
Set Name Test Cases
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 22 ms 924 KB
subtask0_sample_02.txt AC 23 ms 800 KB
subtask1_line01.txt AC 23 ms 668 KB
subtask1_line02.txt AC 23 ms 796 KB
subtask1_line03.txt AC 23 ms 800 KB
subtask1_line04.txt AC 23 ms 796 KB
subtask1_line05.txt AC 24 ms 804 KB
subtask1_line06.txt AC 23 ms 804 KB
subtask1_random01.txt AC 23 ms 788 KB
subtask1_random02.txt AC 22 ms 676 KB
subtask1_random03.txt AC 21 ms 800 KB
subtask1_random04.txt AC 22 ms 796 KB
subtask1_random05.txt AC 23 ms 804 KB
subtask1_random06.txt AC 23 ms 804 KB
subtask1_random07.txt AC 21 ms 732 KB
subtask1_random08.txt AC 22 ms 672 KB
subtask1_special01.txt AC 21 ms 804 KB
subtask1_special02.txt AC 23 ms 676 KB
subtask1_special03.txt AC 23 ms 800 KB
subtask1_special04.txt AC 21 ms 916 KB