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

Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <chrono>
using namespace std;
class Connection;
class City {
public:
int cityID;
bool isField;
bool hasFieldConnection = false;
vector<Connection> connections;
int shortestPath = 999999999;
vector<int> visitedBy;
City(){
this->cityID = -1;
this->isField = false;
connections = vector<Connection>();
visitedBy = vector<int>();
}
City(int cityID, bool isField){
this->cityID = cityID;
this->isField = isField;
connections = vector<Connection>();
visitedBy = vector<int>();
}
void CreateConnection(City& destination, int cost);
};
class Connection
{
public:
City* destination;
int cost;
Connection(City* destination, int cost)
{
this->destination = destination;
this->cost = cost;
}
};
void City::CreateConnection(City &destination, int cost){
connections.push_back(Connection(&destination, cost));
if(destination.isField){
this->hasFieldConnection = true;
}
}
class SearchState{
public:
City* city;
int totalCost;
int startingPort;
SearchState(){}
SearchState(City* city, int totalCost, int startingPort){
this->city = city;
this->totalCost = totalCost;
this->startingPort = startingPort;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// INPUT
int cityCount;
cin >> cityCount;
vector<City> cities(cityCount);
for (int i = 0; i < cityCount; ++i) {
int type;
cin >> type;
cities[i] = City(i, type == 1);
}
for(int i = 0; i < cityCount - 1; i++){
int a, b, c;
cin >> a >> b >> c;
cities[a - 1].CreateConnection(cities[b - 1], c);
cities[b - 1].CreateConnection(cities[a - 1], c);
}
/*int cityCount = 201111;
vector<City> cities(cityCount);
int fieldCount = 0;
int k = 1.2;
for(int i = 0; i < cityCount; i++){
cities[i] = City(i, i < (cityCount / k));
if (i < (cityCount / k)){
fieldCount++;
}
}
for(int i = 0; i < cityCount - 1; i++){
int randomIndex;
do {
randomIndex = rand() % cityCount;
}
while (randomIndex == i);
cities[i].CreateConnection(cities[randomIndex], 1);
cities[randomIndex].CreateConnection(cities[i], 1);
}
cout << "FIELDS: " << fieldCount << "\n";*/
//auto start = std::chrono::high_resolution_clock::now();
// ALG
queue<SearchState> q = queue<SearchState>();
long fieldCount = 0;
for (int i = 0; i < cityCount; i++){
if(!cities[i].isField && cities[i].hasFieldConnection){
vector<int> visited = vector<int>(1);
visited[0] = i;
q.push(SearchState(&cities[i], 0, i));
}
else if (cities[i].isField){
fieldCount += 1;
}
}
long totalLength = fieldCount * 999999999;
while (q.size() > 0)
{
SearchState state = q.front(); q.pop();
if (state.city->shortestPath < state.totalCost){
continue;
}
for (Connection connection : state.city->connections){
if (!connection.destination->isField) { continue; }
if (count(connection.destination->visitedBy.begin(), connection.destination->visitedBy.end(), state.startingPort)) { continue; }
int newCost = state.totalCost + connection.cost;
if(newCost < connection.destination->shortestPath){
totalLength -= connection.destination->shortestPath - newCost;
connection.destination->shortestPath = newCost;
} else { continue; }
connection.destination->visitedBy.push_back(state.startingPort);
SearchState newState = SearchState(connection.destination, newCost, state.startingPort);
q.push(newState);
}
}
//auto end = std::chrono::high_resolution_clock::now();
//cout << "TIME: " << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() / 1000.0 << "\n";
cout << totalLength;
}

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

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

correct output
1795118520

user output
1795118520

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

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

correct output
816932444

user output
816932444

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

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

correct output
40839

user output
40839

Test 12

Group: 2

Verdict: ACCEPTED

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

correct output
5683983203973

user output
5683983203973

Test 13

Group: 2

Verdict: ACCEPTED

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

correct output
58572993

user output
58572993

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

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

correct output
978670626

user output
978670626

Test 22

Group: 2

Verdict: ACCEPTED

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

correct output
375218

user output
375218

Test 23

Group: 2

Verdict: ACCEPTED

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

correct output
60422556

user output
60422556

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

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

correct output
59607954

user output
59607954

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

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

correct output
199982

user output
199982

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

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

correct output
3137875

user output
3137875

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

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

correct output
1652889357

user output
1652889357