CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:Septicuss
Submission time:2022-11-06 16:41:52 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.07 s1, 2details
#2ACCEPTED0.07 s1, 2details
#30.07 s1, 2details
#40.07 s1, 2details
#5ACCEPTED0.07 s1, 2details
#60.18 s1, 2details
#7--2details
#80.17 s1, 2details
#9--2details
#100.19 s1, 2details
#11--2details
#12--2details
#13--2details
#14--2details
#150.17 s1, 2details
#160.17 s1, 2details
#170.18 s1, 2details
#180.17 s1, 2details
#190.17 s1, 2details
#200.18 s1, 2details
#21--2details
#22--2details
#23--2details
#240.17 s1, 2details
#25--2details
#260.18 s1, 2details
#27--2details
#280.17 s1, 2details
#29--2details
#300.17 s1, 2details
#31--2details

Compiler report

Note: input/E4301.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
class E4301 {
static final int K = 1000;
static int N;
static int ANS;
public static void main(String[] args) {
FastReader reader = new FastReader();
PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
N = reader.nextInt();
final List<Integer> ports = new ArrayList<>();
final List<Pair<Integer, Integer>> connections[] = new List[N + 1];
Arrays.fill(connections, new ArrayList<Pair<Integer, Integer>>());
for (int i = 0; i < N; i++) {
if (reader.nextInt() == 0)
ports.add(i);
}
for (int i = 0; i < N - 1; i++) {
int a, b, c;
a = reader.nextInt();
b = reader.nextInt();
c = reader.nextInt();
connections[a].add(new Pair<Integer, Integer>(b, c));
connections[b].add(new Pair<Integer, Integer>(a, c));
}
reader.close();
for (int port : ports) {
connections[N].add(new Pair<Integer, Integer>(port, 0));
}
int[] distance = new int[N + 1];
int[] visited = new int[N + 1];
Arrays.fill(distance, 1001);
Arrays.fill(visited, 0);
Queue<Integer> bfs[] = new LinkedList[K + 1];
Arrays.fill(bfs, new LinkedList<Integer>());
bfs[0].add(N);
distance[N] = 0;
int pos = 0;
int high = 1;
while (high > 0) {
int index = pos % K + 1;
while (bfs[index].isEmpty()) {
pos++;
}
int u = bfs[index].remove();
high -= 1;
if (visited[u] != 0)
continue;
visited[u] = 1;
for (Pair<Integer, Integer> edge : connections[u]) {
int cost = edge.second;
int w = edge.first;
if (distance[u] + cost < distance[w]) {
if (distance[w] == K + 1) {
ANS += distance[u] + cost;
} else {
ANS -= distance[w];
ANS += distance[u] + cost;
}
distance[w] = distance[u] + cost;
bfs[distance[w] % (K + 1)].add(w);
high++;
}
}
}
writer.println(ANS);
writer.flush();
writer.close();
}
static class Pair<K, V> {
K first;
V second;
public Pair(K first, V second) {
this.first = first;
this.second = second;
}
}
static class FastReader {
private BufferedReader br;
private StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.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: ACCEPTED

input
1
0

correct output
0

user output
0

Test 2

Group: 1, 2

Verdict: ACCEPTED

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

correct output
0

user output
0

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
30

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
40

Test 5

Group: 1, 2

Verdict: ACCEPTED

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

correct output
6

user output
6

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
411408

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)

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
192342

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)

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
3844

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)

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)

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)

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)

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
339917

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
161826

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
32959

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
327172

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
37000

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
194514

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)

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)

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)

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
123798

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)

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
500

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)

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
999

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)

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
378218

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)