CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:Zendium
Submission time:2021-10-15 19:57:19 +0300
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.16 s1, 2, 3details
#2--2, 3details
#3--3details

Code

import java.util.ArrayList;
import java.util.Scanner;

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

        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 (koneJoka(fnum) == null)
                kone1 = new Computer(fnum);
            else
                kone1 = koneJoka(fnum);

            Computer kone2;
            if (koneJoka(snum) == null)
                kone2 = new Computer(snum);
            else {
                kone2 = koneJoka(snum);
                koneet.remove(kone2);
            }
            Connection c = new Connection(Long.parseLong(d[2]), new Computer[]{kone1, kone2});
            connections.add(c);
            kone1.add(c);
            kone2.add(c);
            koneet.add(kone1);
            koneet.add(kone2);
        }
        long sum = 0;
        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 (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(koneJoka(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(koneJoka(cCI))].number;
                    ArrayList<Connection> nextInt = koneJoka(cCI).connections;
                    nextInt.remove(nextcon);
                    currentIntersection = new Intersection(cCI, nextInt);
                    connectedTo1++;
                }

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

    public static Computer koneJoka(int i) {
        for (Computer kone : koneet) {
            if (kone.number == i) {
                return kone;
            }
        }
        return null;
    }
}

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(Computer t) {
        return (t == koneet[0])? 1 : 0;
    }
}

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

Test details

Test 1

Group: 1, 2, 3

Verdict:

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

correct output
88687

user output
24343

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)