| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 250996 |
2020-07-19T19:48:52 Z |
A02 |
Dreaming (IOI13_dreaming) |
C++14 |
|
376 ms |
25720 KB |
#include "dreaming.h"
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
pair<long long, long long> calc_centre(int start, vector<vector<pair<long long, long long> > > &adjacent){
queue<long long> to_visit;
to_visit.push(start);
map<long long, long long> distances1;
distances1[start] = 0;
long long longest_distance = 0;
long long endpoint = start;
while (!to_visit.empty()){
long long current = to_visit.front();
if (longest_distance < distances1[current]){
longest_distance = distances1[current];
endpoint = current;
}
to_visit.pop();
for (int j = 0; j < adjacent[current].size(); j++){
if (distances1.find(adjacent[current][j].first) == distances1.end()){
distances1[adjacent[current][j].first] = distances1[current] + adjacent[current][j].second;
to_visit.push(adjacent[current][j].first);
}
}
}
map<long long, long long> distances;
map<long long, long long> parent;
parent[endpoint] = endpoint;
distances[endpoint] = 0;
to_visit.push(endpoint);
longest_distance = 0;
long long startpoint = endpoint;
while (!to_visit.empty()){
long long current = to_visit.front();
if (longest_distance < distances[current]){
longest_distance = distances[current];
startpoint = current;
}
to_visit.pop();
for (long long j = 0; j < adjacent[current].size(); j++){
if (distances.find(adjacent[current][j].first) == distances.end()){
distances[adjacent[current][j].first] = distances[current] + adjacent[current][j].second;
to_visit.push(adjacent[current][j].first);
parent[adjacent[current][j].first] = current;
}
}
}
long long radius = longest_distance;
long long current = startpoint;
long long left_distance = longest_distance;
long long right_distance = 0;
while (current != endpoint){
radius = min(radius, max(left_distance, right_distance));
current = parent[current];
left_distance = distances[current];
right_distance = longest_distance - left_distance;
}
return make_pair(radius, longest_distance);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<long long, long long> > > adjacent (N, vector<pair<long long, long long> > ());
for (int i = 0; i < M; i++){
adjacent[A[i]].push_back(make_pair(B[i], T[i]));
adjacent[B[i]].push_back(make_pair(A[i], T[i]));
}
vector<long long> region (N, -1);
long long current_region = 0;
vector<pair<long long, long long> > radii;
for (int i = 0; i < N; i++){
if (region[i] == -1){
radii.push_back(calc_centre(i, adjacent));
queue<long long> to_visit;
to_visit.push(i);
while (!to_visit.empty()){
long long current = to_visit.front();
to_visit.pop();
region[current] = current_region;
for (long long j = 0; j < adjacent[current].size(); j++){
if (region[adjacent[current][j].first] == -1){
to_visit.push(adjacent[current][j].first);
}
}
}
current_region++;
}
}
cout << radii.size() << endl;
sort(radii.begin(), radii.end());
// while (radii.size() > 1){
//
// pair<long long, long long> a1 = radii[radii.size() - 1];
// pair<long long, long long> a2 = radii[radii.size() - 2];
// radii.pop_back();
// radii.pop_back();
//
// long long r1 = (min(max(a1.first, a2.first + L), max(a2.first, a1.first + L)));
// radii.push_back(make_pair(r1, max(a1.second, max(a2.second, a1.first + a2.first + L))));
//
// }
if(radii.size() == 1){
return radii[0].second;
}
return max(radii[radii.size() - 1].second, radii[radii.size() - 1].first + radii[radii.size() - 2].first + L);
}
Compilation message
dreaming.cpp: In function 'std::pair<long long int, long long int> calc_centre(int, std::vector<std::vector<std::pair<long long int, long long int> > >&)':
dreaming.cpp:34:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < adjacent[current].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:64:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long j = 0; j < adjacent[current].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:120:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long j = 0; j < adjacent[current].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
25720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
25720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
25720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
6728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
25720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
25720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
