CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Septicuss
Submission time:2022-11-02 10:56:52 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.07 s1, 2details
#20.07 s1, 2details
#30.07 s1, 2details
#40.07 s1, 2details
#50.07 s1, 2details
#60.07 s1, 2details
#70.08 s2details
#80.07 s1, 2details
#90.07 s2details
#100.07 s1, 2details
#110.07 s2details
#120.08 s2details
#130.07 s2details
#140.08 s2details
#150.07 s1, 2details
#160.07 s1, 2details
#170.07 s1, 2details
#180.07 s1, 2details
#190.07 s1, 2details
#200.07 s1, 2details
#210.07 s2details
#220.08 s2details
#230.07 s2details
#240.07 s1, 2details
#250.07 s2details
#260.07 s1, 2details
#270.07 s2details
#280.07 s1, 2details
#290.07 s2details
#300.07 s1, 2details
#310.08 s2details

Code

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class E430 {
static int n;
static ArrayList<WeightedNode> ports = new ArrayList<>();
static long[] mins;
public static void main(String[] args) throws FileNotFoundException {
long start = System.currentTimeMillis();
FastReader reader = new FastReader(new FileInputStream(new File("C:/Users/vladi/Desktop/text.txt")));
PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
n = reader.nextInt();
mins = new long[n + 1];
ArrayList<WeightedNode> nodes = new ArrayList<>();
int a, b, c, t;
// City types
for (int id = 1; id < (n + 1); id++) {
t = reader.nextInt();
WeightedNode node = new WeightedNode(id, t, id - 1);
if (t == 0) {
ports.add(node);
}
nodes.add(node);
}
WeightedGraph graph = new WeightedGraph(nodes);
// Connections
for (int i = 0; i < (n - 1); i++) {
a = reader.nextInt() - 1;
b = reader.nextInt() - 1;
c = reader.nextInt();
graph.addWeightedEdge(a, b, c);
}
reader.close();
System.out.println("Input took " + (System.currentTimeMillis() - start) + " ms");
for (WeightedNode port : ports)
graph.dijkstra(port);
long sum = 0;
for (long value : mins) {
sum += value;
}
System.out.println("Solved in " + (System.currentTimeMillis() - start) + " ms");
writer.println(sum);
writer.flush();
writer.close();
}
// ------------------------------------------------------
static long lowestExpense = Long.MAX_VALUE;
static class WeightedGraph {
ArrayList<WeightedNode> nodes = new ArrayList<WeightedNode>();
static PriorityQueue<WeightedNode> queue;
public WeightedGraph(ArrayList<WeightedNode> nodes) {
this.nodes = nodes;
}
void dijkstra(WeightedNode node) {
if (queue == null)
queue = new PriorityQueue<>();
else
queue.clear();
node.distance = 0;
queue.addAll(nodes);
long expense = 0;
while (!queue.isEmpty()) {
if (expense > lowestExpense) {
break;
}
WeightedNode current = queue.remove();
for (WeightedNode neighbor : current.neighbors) {
if (neighbor.type == 0) continue;
if (queue.contains(neighbor)) {
if (neighbor.distance > current.distance + current.weightMap.get(neighbor.id)) {
neighbor.distance = (current.distance + current.weightMap.get(neighbor.id));
if (mins[neighbor.id] != 0) {
mins[neighbor.id] = Math.min(mins[neighbor.id], (long) neighbor.distance);
} else {
mins[neighbor.id] = (long) neighbor.distance;
}
neighbor.parent = current;
expense += neighbor.distance;
lowestExpense = Math.min(lowestExpense, expense);
queue.remove(neighbor);
queue.add(neighbor);
}
}
}
}
}
void addWeightedEdge(int a, int b, int c) {
WeightedNode first = nodes.get(a);
WeightedNode second = nodes.get(b);
first.neighbors.add(second);
first.weightMap.put(second.id, c);
second.neighbors.add(first);
second.weightMap.put(first.id, c);
}
}
static class WeightedNode implements Comparable<WeightedNode> {
int id;
int type;
ArrayList<WeightedNode> neighbors = new ArrayList<>();
HashMap<Integer, Integer> weightMap = new HashMap<>();
boolean visited = false;
WeightedNode parent;
long distance;
int index;
public WeightedNode(int id, int type, int index) {
this.id = id;
this.type = type;
distance = 1001;
this.index = index;
}
@Override
public int compareTo(WeightedNode o) {
return (int) (this.distance - o.distance);
}
}
static class FastReader {
private BufferedReader br;
private StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(InputStream in) {
br = new BufferedReader(new InputStreamReader(in));
}
void close() {
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
st = null;
br = null;
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
int nextInt() {
return Integer.parseInt(next());
}
BigInteger nextBigInteger() {
return new BigInteger(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
long nextLong() {
return Long.parseLong(next());
}
}
}

Test details

Test 1

Group: 1, 2

Verdict:

input
1
0

correct output
0

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 2

Group: 1, 2

Verdict:

input
5
0 0 0 0 0
1 2 1
2 3 2
3 4 3
...

correct output
0

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 3

Group: 1, 2

Verdict:

input
4
1 0 1 1
1 2 10
2 3 20
2 4 30

correct output
60

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 4

Group: 1, 2

Verdict:

input
5
0 1 1 1 0
1 2 10
2 3 20
3 4 30
...

correct output
80

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 5

Group: 1, 2

Verdict:

input
5
0 1 0 1 1
1 2 1
2 3 5
3 4 3
...

correct output
6

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 6

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5506363

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 7

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1795118520

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 8

Group: 1, 2

Verdict:

input
1000
0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ...

correct output
293576

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 9

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
816932444

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 10

Group: 1, 2

Verdict:

input
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
3089

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 11

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
40839

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 12

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5683983203973

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 13

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 ...

correct output
58572993

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 14

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
32755

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 15

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
126238345

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 16

Group: 1, 2

Verdict:

input
1000
0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 ...

correct output
278678

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 17

Group: 1, 2

Verdict:

input
1000
1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ...

correct output
34929

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 18

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1543963

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 19

Group: 1, 2

Verdict:

input
1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
39606

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 20

Group: 1, 2

Verdict:

input
1000
1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ...

correct output
321598

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 21

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
978670626

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 22

Group: 2

Verdict:

input
200000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
375218

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 23

Group: 2

Verdict:

input
200000
1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 ...

correct output
60422556

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 24

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
291990

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 25

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
59607954

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 26

Group: 1, 2

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
990

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 27

Group: 2

Verdict:

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
199982

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 28

Group: 1, 2

Verdict:

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
7987

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 29

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
3137875

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 30

Group: 1, 2

Verdict:

input
1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
4657693

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...

Test 31

Group: 2

Verdict:

input
200000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1652889357

user output
(empty)

Error:
Exception in thread "main" java.io.FileNotFoundException: C:/Users/vladi/Desktop/text.txt...