Task: | Tietoverkko |
Sender: | Zendium |
Submission time: | 2021-10-15 22:59:06 +0300 |
Language: | Java |
Status: | READY |
Result: | 10 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.17 s | 1, 2, 3 | details |
#2 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
import java.lang.reflect.Array;import java.util.ArrayList;import java.util.HashMap;import java.util.Scanner;/*121 2 22 8 58 10 18 9 28 11 100002 3 42 4 34 5 14 6 16 7 711 12 210083* */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<>(); // IndeksitArrayList<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; // currentComputerIndexArrayList<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; // currentComputerIndexintersections = 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: TIME LIMIT EXCEEDED
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: TIME LIMIT EXCEEDED
input |
---|
200000 1 2 613084013 1 3 832364259 2 4 411999902 3 5 989696303 ... |
correct output |
---|
1080549209850010931 |
user output |
---|
(empty) |