#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iostream>
#include <cassert>
#include <bitset>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// template<typename T>
// using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
// template<typename T, typename S>
// using ordered_map = __gnu_pbds::tree<T, S, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename T, typename S>
ostream& operator<< (ostream& out, pair<T, S> p) {
return out << "(" << p.first << ", " << p.second << ")";
}
// any ct except std::string
template<typename Container,
typename S = typename enable_if<!is_same<Container, string>::value, typename Container::value_type>::type>
ostream& operator<<(ostream& __out, Container &__ct) {
__out << "{";
bool first = true;
for(auto&& __el : __ct) {
if(!first) __out << ", ";
__out << __el;
first = false;
}
return __out << "}";
}
// bitset
template<size_t N>
ostream& operator<<(ostream& __out, bitset<N> &__bs) {
__out << "{";
for(size_t i = 0; i < N; ++i) __out << (i != 0 ? ", " : "") /*<< boolalpha*/ << __bs[N - i - 1];
return __out << "}";
}
template<typename Tail>
void _dbg(Tail T) {
cerr << T << '\n';
}
template<typename Head, typename... Tail>
void _dbg(Head H, Tail... T) {
cerr << H << ", ";
_dbg(T...);
}
#ifdef DEBUG
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: "; _dbg(__VA_ARGS__);
#else
#define dbg(...) 42
#endif
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vii> AL(N, vii());
for(int i = 0; i < M; ++i) {
AL[A[i]].emplace_back(B[i], T[i]);
AL[B[i]].emplace_back(A[i], T[i]);
}
vi visited(N, -1);
vi sizes;
unordered_map<int, int> dist;
// calcola le distanze dei cc
for(int start = 0; start < N; ++start) {
// non visitato
if(visited[start] == -1) {
// calcola longest path, ricalcolala, prova tutti i nodi in mezzo alla strada piu' lunga
dist.clear();
visited[start] = true;
// parti da u
queue<int> q;
dist[start] = 0;
q.emplace(start);
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto &[v, w] : AL[u]) {
if(dist.find(v) == dist.end()) {
dist[v] = dist[u] + w; // una sola strada possibile
visited[v] = true;
q.emplace(v);
}
}
}
dbg(dist);
int furthest = max_element(dist.begin(), dist.end(), [](const ii &a, const ii &b){
if(a.second == b.second) {
return a.first < b.first;
}
return a.second < b.second;
})->first; // trova l'elemento piu' distante
// rigira la bfs partendo dal piu' distante
dist.clear();
dist[furthest] = 0;
q.emplace(furthest);
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto &[v, w] : AL[u]) {
if(dist.find(v) == dist.end()) {
dist[v] = dist[u] + w; // una sola strada possibile
q.emplace(v);
}
}
}
dbg(dist);
int end = max_element(dist.begin(), dist.end(), [](const ii &a, const ii &b){
if(a.second == b.second) {
return a.first < b.first;
}
return a.second < b.second;
})->first; // trova l'elemento piu' distante
dbg(end);
int to = end;
// percorri tutti i nodi tra start ed end, trova il migliore
int best = dist[to];
while(furthest != to) {
// avvicinati ad end
int next = AL[to][0].first;
int next_dist = dist[next];
for(auto &[v, w] : AL[to]) {
if(dist[v] < next_dist) {
next = v;
next_dist = dist[v];
}
}
to = next;
best = min(best, max(dist[to], dist[end] - dist[to]));
}
sizes.push_back(best);
}
}
assert(sizes.size() > 1);
if(sizes.size() == 1) {
return 0;
}
else {
sort(sizes.rbegin(), sizes.rend());
return sizes[0] + L + sizes[1];
}
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:58:18: warning: statement has no effect [-Wunused-value]
58 | #define dbg(...) 42
| ^~
dreaming.cpp:103:13: note: in expansion of macro 'dbg'
103 | dbg(dist);
| ^~~
dreaming.cpp:58:18: warning: statement has no effect [-Wunused-value]
58 | #define dbg(...) 42
| ^~
dreaming.cpp:128:13: note: in expansion of macro 'dbg'
128 | dbg(dist);
| ^~~
dreaming.cpp:58:18: warning: statement has no effect [-Wunused-value]
58 | #define dbg(...) 42
| ^~
dreaming.cpp:137:13: note: in expansion of macro 'dbg'
137 | dbg(end);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
11416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
11416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
5500 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
5604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
11416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
