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
Task B - ツリーグラフ
User nida_001
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1718 Byte
Status AC
Exec Time 24 ms
Memory 924 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 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