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
AC × 3
AC × 14
AC × 11
AC × 48
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