CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:andreibe
Submission time:2021-10-08 18:52:41
Language:Java
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.17 s1, 2, 3details
#2--2, 3details
#3--3details

Code

import java.util.ArrayList;
import java.util.Scanner;
class Pair {
    public final int key;
    public final int value;

    public Pair(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class Main {
    static ArrayList<ArrayList<Pair>> tree;
    static int total;
    static boolean[] kayty;
    static int n;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        tree = new ArrayList<>(n+1);
        for (int i = 0; i < n+1; i++) {
            tree.add(new ArrayList<>());
        }
        kayty = new boolean[n+1];
        for (int i = 0; i < n-1; i++) {
            int a = Integer.parseInt(input.next());
            int b = Integer.parseInt(input.next());
            int x = Integer.parseInt(input.next());
            ArrayList<Pair> neighbors = tree.get(a);
            ArrayList<Pair> neighbors2 = tree.get(b);
            neighbors.add(new Pair(b,x));
            neighbors2.add(new Pair(a,x));
        }
        for (int i = 0; i < tree.size(); i++) {
            kayty = new boolean[n+1];
            kayty[i] = true;
            count(i,Integer.MAX_VALUE);
        }
        System.out.println(total/2);
    }
    private static void count(int index, int min) {
        ArrayList<Pair> naapurit = tree.get(index);
        kayty[index] = true;
        for (Pair naapuri : naapurit) {
            if (!kayty[naapuri.key]) {
                int val = Math.min(min,naapuri.value);
                total += val;
                count(naapuri.key,val);
            }
        }
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)