CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:Zendium
Submission time:2021-10-15 22:59:06 +0300
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.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

/*
12
1 2 2
2 8 5
8 10 1
8 9 2
8 11 10000
2 3 4
2 4 3
4 5 1
4 6 1
6 7 7
11 12 2

10083
* */
public class Viides {
    public static ArrayList<Connection> connections;
    public static void main(String[] args) {
        connections = new ArrayList<>();
        //HashMap<int[], Long> network = new HashMap<>();
        Scanner s = new Scanner(System.in);
        int largestNumber = Integer.parseInt(s.nextLine());
        Computer[] computers = new Computer[largestNumber];

        for (int i = 0; i < largestNumber - 1; i++) {
            String[] d = s.nextLine().split(" ");
            //network.put(new int[]{Integer.parseInt(d[0]), Integer.parseInt(d[1])}, Long.parseLong(d[2]));
            int fnum = Integer.parseInt(d[0]);
            int snum = Integer.parseInt(d[1]);

            Computer kone1;
            if (computers[fnum - 1] == null)
                kone1 = new Computer(fnum);
            else {
                kone1 = computers[fnum - 1];
            }

            Computer kone2;
            if (computers[snum - 1] == null)
                kone2 = new Computer(snum);
            else {
                kone2 = computers[snum - 1];
            }
            Connection c = new Connection(Long.parseLong(d[2]), new Computer[]{kone1, kone2});
            connections.add(c);
            kone1.add(c);
            kone2.add(c);
            computers[fnum - 1] = kone1;
            computers[snum - 1] = kone2;
        }
        long sum = 0;

        for (Computer computer : computers) {
            computer.done = true;
            ArrayList<Integer> toDoList = new ArrayList<>();    // Indeksit
            ArrayList<Long> toDoLengthSaves = new ArrayList<>();
            boolean[] done = new boolean[largestNumber];
            int amountDone = 0;

            int cCI = computer.number;
            long currentSmallestLength = 1000000001;
            while (amountDone < largestNumber) {
                for (Connection connection : computers[cCI - 1].connections) {
                    int pcIndex = connection.koneet[connection.notI(cCI)].number;
                    if (!done[pcIndex - 1]) {
                        long nextSmallestLength = currentSmallestLength;
                        if (nextSmallestLength > connection.length) nextSmallestLength = connection.length;
                        if (!connection.koneet[connection.notI(cCI)].done) sum+=nextSmallestLength;
                        toDoLengthSaves.add(nextSmallestLength);
                        toDoList.add(pcIndex);
                    }
                }

                done[cCI - 1] = true;
                amountDone++;
                if (toDoList.size() > 0) {
                    currentSmallestLength = toDoLengthSaves.get(0);
                    cCI = toDoList.get(0);
                    toDoLengthSaves.remove(0);
                    toDoList.remove(0);
                }
            }

        }

        // Toinen algo

        /*
        ArrayList<Connection> bumpedConnections = new ArrayList<>();

        for (Connection connection : connections) {
            long minlength = connection.length;

            int cCI = connection.koneet[0].number; // currentComputerIndex

            ArrayList<Intersection> intersections = new ArrayList<>();
            Intersection currentIntersection = new Intersection(cCI, koneJoka(cCI).connections);
            int connectedTo0 = 1;
            while (true) {
                System.out.println("0: " + cCI);
                ArrayList<Connection> viableConnections = new ArrayList<>();
                for (Connection con : currentIntersection.remainingConnections) {
                    if (con.length >= minlength) {
                        viableConnections.add(con);
                        if (con.length == minlength) {
                            con.bumps[con.notI(cCI)] += connection.bumps
                        }
                    }
                }
                if (viableConnections.size() <= 0) {
                    if (intersections.size() > 0) {
                        currentIntersection = intersections.get(intersections.size() - 1);
                        cCI = currentIntersection.index;
                        intersections.remove(intersections.size() - 1);
                        System.out.println("jump to " + cCI);
                    } else break;
                } else {
                    Connection nextcon = viableConnections.get(0);
                    viableConnections.remove(0);
                    if (viableConnections.size() > 0) {
                        intersections.add(new Intersection(cCI, viableConnections));
                    }
                    cCI = nextcon.koneet[nextcon.notI(cCI)].number;
                    ArrayList<Connection> nextInt = koneJoka(cCI).connections;
                    nextInt.remove(nextcon);
                    currentIntersection = new Intersection(cCI, nextInt);
                    connectedTo0++;
                }

            }
            System.out.println("Con0 " + connectedTo0);
            cCI = connection.koneet[1].number; // currentComputerIndex

            intersections = new ArrayList<>();
            currentIntersection = new Intersection(cCI, koneJoka(cCI).connections);
            int connectedTo1 = 1;
            while (true) {
                System.out.println("1: " + cCI);
                ArrayList<Connection> viableConnections = new ArrayList<>();
                for (Connection con : currentIntersection.remainingConnections) {
                    if (con.length > minlength) {
                        viableConnections.add(con);
                    }
                }
                if (viableConnections.size() <= 0) {
                    if (intersections.size() > 0) {
                        currentIntersection = intersections.get(intersections.size() - 1);
                        cCI = currentIntersection.index;
                        intersections.remove(intersections.size() - 1);
                        System.out.println("jump to " + cCI);
                    } else break;
                } else {
                    Connection nextcon = viableConnections.get(0);
                    viableConnections.remove(0);
                    if (viableConnections.size() > 0) {
                        intersections.add(new Intersection(cCI, viableConnections));
                    }
                    cCI = nextcon.koneet[nextcon.notI(cCI)].number;
                    ArrayList<Connection> nextInt = koneJoka(cCI).connections;
                    nextInt.remove(nextcon);
                    currentIntersection = new Intersection(cCI, nextInt);
                    connectedTo1++;
                }

            }
            connection.connectedTo0 = connectedTo0;
            connection.connectedTo1 = connectedTo1;
            System.out.println("Con1 " + connectedTo1);
            sum+=connectedTo0*connectedTo1*minlength;
            System.out.println("Sum " + sum);
        }

         */
        System.out.println(sum);
    }

}
/*
class Intersection {
    public ArrayList<Connection> remainingConnections;
    public int index;
    public Intersection(int number, ArrayList<Connection> con) {
        remainingConnections = con;
        index = number;
    }
}
*/
class Connection {
    public Computer[] koneet;
    public long length;
    public Connection(long l, Computer[] k) {
       koneet = k;
       length = l;
    }
    public int notI(int nmb) {
        return (nmb == koneet[0].number)? 1 : 0;
    }
}

class Computer {
    public int number;
    public ArrayList<Connection> connections;
    public boolean done;
    public Computer(int i) {
        number = i;
        connections = new ArrayList<>();
        done = false;
    }
    public void add(Connection c) {
        connections.add(c);
    }
}

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)