Submission #1476621
Source Code Expand
#include <iostream> #include <queue> #include <vector> #include <cmath> #include <algorithm> #include <map> using namespace std; using ll = long long; const ll INF = 1e9; int N; vector<bool> H(101, false); map<int, vector<int>> G; map<int, vector<int>> U; bool decide(int cur, int parent) { bool use_cur = false; for (auto i : G[cur]) { if (i == parent) continue; if (H[i]) { U[cur].push_back(i); use_cur = true; } if (decide(i, cur)) { use_cur = true; } } if (use_cur) { U[parent].push_back(cur); } return use_cur; } int steps(int cur, int parent) { int ret = 0; for (auto i : G[cur]) { if (i == parent) continue; for (auto j : U[cur]) { if (i == j) { ret += 2; break; } } ret += steps(i, cur); } return ret; } int main() { int X; cin >> N >> X; H.resize(N+1); for (int i = 0; i < N; i++) { int a; cin >> a; H[i+1] = (a == 1); } for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } decide(X, -1); cout << steps(X, -1) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - ツリーグラフ |
User | sei0o |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1369 Byte |
Status | AC |
Exec Time | 2 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
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 | 1 ms | 256 KB |
subtask0_sample_02.txt | AC | 1 ms | 256 KB |
subtask1_line01.txt | AC | 1 ms | 256 KB |
subtask1_line02.txt | AC | 1 ms | 256 KB |
subtask1_line03.txt | AC | 1 ms | 256 KB |
subtask1_line04.txt | AC | 1 ms | 256 KB |
subtask1_line05.txt | AC | 1 ms | 256 KB |
subtask1_line06.txt | AC | 1 ms | 256 KB |
subtask1_random01.txt | AC | 1 ms | 256 KB |
subtask1_random02.txt | AC | 1 ms | 256 KB |
subtask1_random03.txt | AC | 1 ms | 256 KB |
subtask1_random04.txt | AC | 1 ms | 256 KB |
subtask1_random05.txt | AC | 1 ms | 256 KB |
subtask1_random06.txt | AC | 1 ms | 256 KB |
subtask1_random07.txt | AC | 1 ms | 256 KB |
subtask1_random08.txt | AC | 1 ms | 256 KB |
subtask1_special01.txt | AC | 1 ms | 256 KB |
subtask1_special02.txt | AC | 1 ms | 256 KB |
subtask1_special03.txt | AC | 1 ms | 256 KB |
subtask1_special04.txt | AC | 2 ms | 384 KB |