Submission #286884


Source Code Expand

Copy
#include <iostream>
#include <vector>

using namespace std;

class Solver {
    public:
        int n, x;
        int h[100], a[100], b[100];
        vector<int> next_nodes[100];
        int dfs(int current, int parent=-1) {
            int distance = 0;
            for (int i = 0; i < (int)next_nodes[current].size(); ++i) {
                int nn = next_nodes[current][i];
                if (nn != parent) {
                    int d = dfs(nn, current);
                    if (d > 0 || h[nn] > 0) {
                        distance += 1 + d;
                    }
                }
            }
            return distance;
        }
        int solve() {
            for (int i = 0; i < n; ++i) {
                next_nodes[i].clear();
            }
            for (int i = 0; i < n - 1; ++i) {
                next_nodes[a[i] - 1].push_back(b[i] - 1);
                next_nodes[b[i] - 1].push_back(a[i] - 1);
            }
            return dfs(x - 1) * 2;
        }
};

int main() {
    Solver s;
    cin >> s.n >> s.x;
    for (int i = 0; i < s.n; ++i) {
        cin >> s.h[i];
    }
    for (int i = 0; i < s.n - 1; ++i) {
        cin >> s.a[i] >> s.b[i];
    }
    cout << s.solve() << endl;
    return 0;
}

Submission Info

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