CSES - Datatähti 2023 alku - Results
Submission details
Task:Sadonkorjuu
Sender:DualRed
Submission time:2022-11-01 22:23:30 +0200
Language:Java
Status:READY
Result:33
Feedback
groupverdictscore
#1ACCEPTED33
#20
Test results
testverdicttimegroup
#1ACCEPTED0.07 s1, 2details
#2ACCEPTED0.07 s1, 2details
#3ACCEPTED0.07 s1, 2details
#4ACCEPTED0.07 s1, 2details
#5ACCEPTED0.07 s1, 2details
#6ACCEPTED0.11 s1, 2details
#7--2details
#8ACCEPTED0.12 s1, 2details
#9--2details
#10ACCEPTED0.12 s1, 2details
#11--2details
#12--2details
#13--2details
#14ACCEPTED0.97 s2details
#15ACCEPTED0.14 s1, 2details
#16ACCEPTED0.12 s1, 2details
#17ACCEPTED0.11 s1, 2details
#18ACCEPTED0.12 s1, 2details
#19ACCEPTED0.11 s1, 2details
#20ACCEPTED0.12 s1, 2details
#21--2details
#22--2details
#23--2details
#24ACCEPTED0.12 s1, 2details
#25--2details
#26ACCEPTED0.12 s1, 2details
#27--2details
#28ACCEPTED0.12 s1, 2details
#29--2details
#30ACCEPTED0.13 s1, 2details
#31--2details

Code

import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
Solver solver = new Solver();
System.out.println(solver.Solve());
}
}
class Solver{
public int Solve() throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
// INPUT
int cityCount = Integer.parseInt(bufferedReader.readLine());
String[] cityTypes = bufferedReader.readLine().split(" ");
City[] cities = new City[cityCount];
for(int i = 0; i < cityCount; i++){
cities[i] = new City(i, Integer.parseInt(cityTypes[i]) == 1);
}
for(int i = 0; i < cityCount - 1; i++){
String[] inp = bufferedReader.readLine().split(" ");
cities[Integer.parseInt(inp[0]) - 1].AddConnection(cities[Integer.parseInt(inp[1]) - 1], Integer.parseInt(inp[2]));
cities[Integer.parseInt(inp[1]) - 1].AddConnection(cities[Integer.parseInt(inp[0]) - 1], Integer.parseInt(inp[2]));
}
// test generator
/*int cityCount = 200000;
City[] cities = new City[cityCount];
for(int i = 0; i < cityCount; i++){
cities[i] = new City(i, i < cityCount / 2); // amount of fields
}
for(int i = 0; i < cityCount - 1; i++){
Random random = new Random();
int randomIndex;
do {
randomIndex = random.nextInt(cityCount);
}
while (randomIndex == i);
String[] inp = {String.valueOf(i), String.valueOf(randomIndex), "1"};
cities[Integer.parseInt(inp[0])].AddConnection(cities[Integer.parseInt(inp[1])], Integer.parseInt(inp[2]));
cities[Integer.parseInt(inp[1])].AddConnection(cities[Integer.parseInt(inp[0])], Integer.parseInt(inp[2]));
}*/
//long start = System.currentTimeMillis();
// ALG
Queue<SearchState> q = new LinkedList<>();
for(int i = 0; i < cityCount; i++){
if(!cities[i].isField){
List<Integer> visited = new ArrayList<>(1);
visited.add(i);
q.add(new SearchState(cities[i], 0, visited));
}
}
while (q.size() > 0) {
SearchState state = q.poll();
for (Connection connection : state.city.connections) {
int thisID = connection.destination.cityID;
if (state.visited.contains(thisID)) { continue; }
int newCost = state.totalCost + connection.cost;
if (!connection.destination.isField) { continue; }
else {
if (newCost < connection.destination.shortestPath){
connection.destination.shortestPath = newCost;
} else { continue; }
}
state.visited.add(connection.destination.cityID);
q.add(new SearchState(connection.destination, newCost, new ArrayList<Integer>(state.visited)));
}
}
// Count
int totalLength = 0;
for(int i = 0; i < cityCount; i++){
if (cities[i].isField){
//System.out.println(String.valueOf(i) + " -> " + String.valueOf(cities[i].shortestPath));
totalLength += cities[i].shortestPath;
}
}
//System.out.println((System.currentTimeMillis() - start) / 1000.0);
return totalLength;
}
class SearchState {
public City city;
public int totalCost;
public List<Integer> visited = new ArrayList<>();
public SearchState(City city, int totalCost, List<Integer> visited){
this.city = city;
this.visited = visited;
this.totalCost = totalCost;
}
}
public int Solve2() throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
// INPUT
/*int cityCount = Integer.parseInt(bufferedReader.readLine());
String[] cityTypes = bufferedReader.readLine().split(" ");
City[] cities = new City[cityCount];
for(int i = 0; i < cityCount; i++){
cities[i] = new City(i, Integer.parseInt(cityTypes[i]) == 1);
}
for(int i = 0; i < cityCount - 1; i++){
String[] inp = bufferedReader.readLine().split(" ");
cities[Integer.parseInt(inp[0]) - 1].AddConnection(cities[Integer.parseInt(inp[1]) - 1], Integer.parseInt(inp[2]));
cities[Integer.parseInt(inp[1]) - 1].AddConnection(cities[Integer.parseInt(inp[0]) - 1], Integer.parseInt(inp[2]));
}*/
// test generator
int cityCount = 200000;
City[] cities = new City[cityCount];
for(int i = 0; i < cityCount; i++){
cities[i] = new City(i, i < 200000 / 2.5); // amount of fields
}
for(int i = 0; i < cityCount - 1; i++){
Random random = new Random();
int randomIndex;
do {
randomIndex = random.nextInt(cityCount);
}
while (randomIndex == i);
String[] inp = {String.valueOf(i), String.valueOf(randomIndex), "1"};
cities[Integer.parseInt(inp[0])].AddConnection(cities[Integer.parseInt(inp[1])], Integer.parseInt(inp[2]));
cities[Integer.parseInt(inp[1])].AddConnection(cities[Integer.parseInt(inp[0])], Integer.parseInt(inp[2]));
}
long start = System.currentTimeMillis();
// ALG
for(int i = 0; i < cityCount; i++){
if (!cities[i].isField){
if(!cities[i].HasFieldConnection()){
continue;
}
boolean[] usedFlags = new boolean[cityCount];
CalculateShortestPaths(cities[i], 0, usedFlags);
}
}
// Count
int totalLength = 0;
for(int i = 0; i < cityCount; i++){
if (cities[i].isField){
//System.out.println(String.valueOf(i) + " -> " + String.valueOf(cities[i].shortestPath));
totalLength += cities[i].shortestPath;
}
}
System.out.println((System.currentTimeMillis() - start) / 1000.0);
return totalLength;
}
void CalculateShortestPaths(City city, int totalCost, boolean[] usedFlags){
for (Connection connection : city.connections) {
int thisID = connection.destination.cityID;
if (usedFlags[thisID]) { continue; }
int newCost = totalCost + connection.cost;
if (!connection.destination.isField) { continue; }
else {
if (newCost < connection.destination.shortestPath){
connection.destination.shortestPath = newCost;
} else { continue; }
}
usedFlags[thisID] = true;
CalculateShortestPaths(connection.destination, newCost, usedFlags);
usedFlags[thisID] = false;
}
}
class City {
public int cityID;
public boolean isField;
public List<Connection> connections;
public int shortestPath = Integer.MAX_VALUE;
public City(int cityID, boolean isField){
this.cityID = cityID;
this.isField = isField;
connections = new ArrayList<Connection>();
}
public void AddConnection(City destination, int cost) {
connections.add(new Connection(destination, cost));
}
public boolean HasFieldConnection() {
boolean flag = false;
for(int i = 0; i < connections.size(); i++){
if (connections.get(i).destination.isField){
flag = true;
break;
}
}
return flag;
}
}
class Connection {
public City destination;
public int cost;
public Connection(City destination, int cost){
this.destination = destination;
this.cost = cost;
}
}
}

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: ACCEPTED

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

correct output
60

user output
60

Test 4

Group: 1, 2

Verdict: ACCEPTED

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

correct output
80

user output
80

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: ACCEPTED

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

correct output
5506363

user output
5506363

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: ACCEPTED

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

correct output
293576

user output
293576

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: ACCEPTED

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

correct output
3089

user output
3089

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: ACCEPTED

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

correct output
32755

user output
32755

Test 15

Group: 1, 2

Verdict: ACCEPTED

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

correct output
126238345

user output
126238345

Test 16

Group: 1, 2

Verdict: ACCEPTED

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

correct output
278678

user output
278678

Test 17

Group: 1, 2

Verdict: ACCEPTED

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

correct output
34929

user output
34929

Test 18

Group: 1, 2

Verdict: ACCEPTED

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

correct output
1543963

user output
1543963

Test 19

Group: 1, 2

Verdict: ACCEPTED

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

correct output
39606

user output
39606

Test 20

Group: 1, 2

Verdict: ACCEPTED

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

correct output
321598

user output
321598

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: ACCEPTED

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

correct output
291990

user output
291990

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: ACCEPTED

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

correct output
990

user output
990

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: ACCEPTED

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

correct output
7987

user output
7987

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: ACCEPTED

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

correct output
4657693

user output
4657693

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)