Submission #2583293
Source Code Expand
import java.util.Arrays; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Scanner; class Main{ static class Edge{ int[] v=new int[2]; int[] cnt=new int[2]; long w; Edge(int u1,int u2){v[0]=u1;v[1]=u2;} } static List<Edge> edges[]; static boolean[] used; static int dfs(int v){ used[v]=true; int res =1; for(Edge e : edges[v]){ int i = e.v[0]==v ? 1:0; if(used[e.v[i]])continue; e.cnt[i]=dfs(e.v[i]); res += e.cnt[i]; } return res; } static long dfs2(int v){ used[v]=true; long res =0; for(Edge e: edges[v]){ int i = e.v[0]==v ? 1:0; if(used[e.v[i]])continue; res += dfs2(e.v[i]); res += e.w*(long)e.cnt[i]; } return res; } public static void main(String[] args){ Scanner scan = new Scanner(System.in); int N = scan.nextInt(); edges = new ArrayList[N]; used = new boolean[N]; List<Edge> edgeList = new ArrayList<>(); for(int i=0;i<N;++i)edges[i]=new ArrayList<>(); for(int i=0;i<N-1;++i){ int a = scan.nextInt()-1; int b = scan.nextInt()-1; Edge e = new Edge(a, b); edgeList.add(e); edges[a].add(e); edges[b].add(e); } long[] s = new long[N]; for(int i=0;i<N;++i)s[i]=scan.nextLong(); dfs(0); for(Edge e: edgeList){ if(e.cnt[0]==0)e.cnt[0]=N-e.cnt[1]; else e.cnt[1]=N-e.cnt[0]; } Edge equal=null; for(Edge e:edgeList){ if(e.cnt[0]==e.cnt[1]){ equal=e; e.w=0; } else e.w = ((s[e.v[0]] - s[e.v[1]])/((long)(e.cnt[1]-e.cnt[0]))); } if(equal != null){ Arrays.fill(used, false); // System.out.println(dfs2(equal.v[0])); equal.w = (s[equal.v[0]] - dfs2(equal.v[0])) / (equal.cnt[0]); } for(Edge e:edgeList)System.out.println(e.w); } }
Submission Info
Submission Time | |
---|---|
Task | D - Ancient Tree Record |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 800 |
Code Size | 2260 Byte |
Status | AC |
Exec Time | 1494 ms |
Memory | 130140 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | 200 / 200 | 300 / 300 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt |
Subtask2 | 00_example_02.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s3_24.txt, s3_25.txt, s3_26.txt, s3_27.txt, s3_28.txt, s3_29.txt, s3_30.txt, s3_31.txt, s3_32.txt, s3_33.txt, s3_34.txt, s3_35.txt, s3_36.txt, s3_37.txt, s3_38.txt, s3_39.txt, s3_40.txt, s3_41.txt, s3_42.txt, s3_43.txt, s3_44.txt, s3_45.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 92 ms | 21716 KB |
00_example_02.txt | AC | 92 ms | 21076 KB |
00_example_03.txt | AC | 95 ms | 21844 KB |
s1_01.txt | AC | 1095 ms | 104524 KB |
s1_02.txt | AC | 1218 ms | 117176 KB |
s1_03.txt | AC | 260 ms | 37048 KB |
s1_04.txt | AC | 1067 ms | 110396 KB |
s1_05.txt | AC | 455 ms | 42852 KB |
s1_06.txt | AC | 1372 ms | 130140 KB |
s1_07.txt | AC | 1394 ms | 128780 KB |
s1_08.txt | AC | 1375 ms | 129400 KB |
s1_09.txt | AC | 91 ms | 19924 KB |
s1_10.txt | AC | 228 ms | 19924 KB |
s1_11.txt | AC | 99 ms | 21844 KB |
s1_12.txt | AC | 99 ms | 21844 KB |
s1_13.txt | AC | 95 ms | 19924 KB |
s2_14.txt | AC | 936 ms | 90432 KB |
s2_15.txt | AC | 1153 ms | 105484 KB |
s2_16.txt | AC | 1284 ms | 115624 KB |
s2_17.txt | AC | 1379 ms | 118960 KB |
s2_18.txt | AC | 1423 ms | 116908 KB |
s2_19.txt | AC | 1347 ms | 119468 KB |
s2_20.txt | AC | 106 ms | 19796 KB |
s2_21.txt | AC | 100 ms | 21076 KB |
s2_22.txt | AC | 108 ms | 19924 KB |
s2_23.txt | AC | 97 ms | 18896 KB |
s3_24.txt | AC | 1035 ms | 90924 KB |
s3_25.txt | AC | 1159 ms | 106000 KB |
s3_26.txt | AC | 284 ms | 36828 KB |
s3_27.txt | AC | 1065 ms | 101420 KB |
s3_28.txt | AC | 429 ms | 43580 KB |
s3_29.txt | AC | 1407 ms | 118916 KB |
s3_30.txt | AC | 1398 ms | 118512 KB |
s3_31.txt | AC | 1413 ms | 118908 KB |
s3_32.txt | AC | 1494 ms | 125500 KB |
s3_33.txt | AC | 1455 ms | 126864 KB |
s3_34.txt | AC | 1430 ms | 121952 KB |
s3_35.txt | AC | 1421 ms | 120084 KB |
s3_36.txt | AC | 95 ms | 20820 KB |
s3_37.txt | AC | 100 ms | 21716 KB |
s3_38.txt | AC | 113 ms | 18516 KB |
s3_39.txt | AC | 97 ms | 23764 KB |
s3_40.txt | AC | 1039 ms | 101992 KB |
s3_41.txt | AC | 1172 ms | 105000 KB |
s3_42.txt | AC | 292 ms | 33088 KB |
s3_43.txt | AC | 1424 ms | 118608 KB |
s3_44.txt | AC | 1406 ms | 118740 KB |
s3_45.txt | AC | 1420 ms | 119212 KB |