Submission #286721
Source Code Expand
import java.util.ArrayList; import java.util.Scanner; public class Main { @SuppressWarnings("unchecked") public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int x = sc.nextInt()-1; int[] h = new int[n]; for(int i=0;i<n;i++) { h[i] = sc.nextInt(); } ArrayList<Integer>[] edge = new ArrayList[n]; for(int i=0;i<n;i++) { edge[i] = new ArrayList<>(); } for(int i=0;i<n-1;i++) { int a = sc.nextInt()-1; int b = sc.nextInt()-1; edge[a].add(b); edge[b].add(a); } int ans = Integer.MAX_VALUE; ans = Math.min(ans, dfs(-1,x,edge,h)); if (ans < 0) { ans = 0; } System.out.println(ans); } public static int dfs(int parent,int v,ArrayList<Integer>[] edge,int[] h) { int ret = 0; for(int u:edge[v]) { if (u == parent) { continue; } int c = dfs(v, u, edge, h); if (c >= 0) { ret += c + 2; } } if (ret == 0 && h[v] == 0) { return -1; } return ret; } }
Submission Info
Submission Time | |
---|---|
Task | B - ツリーグラフ |
User | piroz95 |
Language | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 1032 Byte |
Status | AC |
Exec Time | 513 ms |
Memory | 24108 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 | 479 ms | 23304 KB |
subtask0_sample_02.txt | AC | 472 ms | 23312 KB |
subtask1_line01.txt | AC | 462 ms | 23108 KB |
subtask1_line02.txt | AC | 489 ms | 23928 KB |
subtask1_line03.txt | AC | 493 ms | 23816 KB |
subtask1_line04.txt | AC | 487 ms | 24108 KB |
subtask1_line05.txt | AC | 497 ms | 24084 KB |
subtask1_line06.txt | AC | 488 ms | 24040 KB |
subtask1_random01.txt | AC | 486 ms | 23860 KB |
subtask1_random02.txt | AC | 485 ms | 23848 KB |
subtask1_random03.txt | AC | 491 ms | 23772 KB |
subtask1_random04.txt | AC | 479 ms | 23984 KB |
subtask1_random05.txt | AC | 495 ms | 23976 KB |
subtask1_random06.txt | AC | 490 ms | 24024 KB |
subtask1_random07.txt | AC | 490 ms | 24108 KB |
subtask1_random08.txt | AC | 488 ms | 24024 KB |
subtask1_special01.txt | AC | 464 ms | 23172 KB |
subtask1_special02.txt | AC | 501 ms | 24028 KB |
subtask1_special03.txt | AC | 513 ms | 23984 KB |
subtask1_special04.txt | AC | 492 ms | 23852 KB |