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)