#include"dreaming.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int u, w;
};
struct tpos
{
int nodo, dist, padre;
};
int max_tam;
vector<vector<edge>> adj;
pair<int, int> bfs (int nodo, int N)
{
// cout << "nodo: " << nodo << '\n';
pair<int, int> ret;
ret.second = -1;
queue<tpos> q;
q.push({nodo, 0, -1});
tpos temp_tpos;
vector<bool> visi(N);
while (!q.empty())
{
temp_tpos = q.front(); q.pop();
visi[temp_tpos.nodo] = 1;
//cout << " " << temp_tpos.nodo << " " << temp_tpos.dist << "\n";
for (edge e: adj[temp_tpos.nodo])
{
// cout << temp_tpos.nodo << " vecinos: " << e.u << '\n';
if (visi[e.u]) continue;
q.push({e.u, temp_tpos.dist+e.w, temp_tpos.nodo});
}
if (temp_tpos.dist > ret.second)
{
ret.second = temp_tpos.dist;
ret.first = temp_tpos.nodo;
}
}
//cout << '\n';
return ret;
}
int Diametro (int N)
{
int ve = bfs(0, N).first;
return bfs(ve, N).second;
}
struct dsu
{
struct componente
{
int representante;
int inicio_diametro, fin_diametro;
int punto_medio, distancia_punto_medio;
vector <int> miembros;
int diametro;
map<int, int> distancia_diametro1, distancia_diametro2;
void BFS (int nodo)
{
queue<tpos> q;
q.push({nodo, 0, -1});
vector<bool> visi(max_tam);
tpos temp_tpos;
while (!q.empty())
{
temp_tpos = q.front(); q.pop();
visi[temp_tpos.nodo] = 1;
distancia_diametro2[temp_tpos.nodo] = temp_tpos.dist;
for (edge e: adj[temp_tpos.nodo])
{
if (visi[e.u]) continue;
q.push({e.u, temp_tpos.dist+e.w, temp_tpos.nodo});
}
}
}
pair<int, int> other_bfs (int nodo, bool pasada)
{
pair<int, int> ret;
ret.second = -1;
queue<tpos> q;
q.push({nodo, 0, -1});
vector<bool> visi(max_tam);
tpos temp_tpos;
while (!q.empty())
{
temp_tpos = q.front(); q.pop();
visi[temp_tpos.nodo] = 1;
if (pasada)
distancia_diametro1[temp_tpos.nodo] = temp_tpos.dist;
for (edge e: adj[temp_tpos.nodo])
{
if (visi[e.u]) continue;
q.push({e.u, temp_tpos.dist+e.w, temp_tpos.nodo});
}
if (temp_tpos.dist > ret.second)
{
ret.second = temp_tpos.dist;
ret.first = temp_tpos.nodo;
}
}
return ret;
}
void get_punto_medio ()
{
int mini = 1<<30;
BFS(fin_diametro);
for (int i = 0; i < miembros.size(); i++)
{
int temp_dist = distancia_diametro1[miembros[i]];
// cout << miembros[i] << " -> " << temp_dist << '\n';
int temp_longlong = max(temp_dist, distancia_diametro2[miembros[i]]);
if (mini > temp_longlong)
{
mini = temp_longlong;
punto_medio = miembros[i];
}
distancia_punto_medio = mini;
}
}
void get_diametro()
{
int resp = other_bfs(representante, 0).first;
inicio_diametro = resp;
pair<int, int> temp_pair = other_bfs(resp, 1);
fin_diametro = temp_pair.first;
diametro = temp_pair.second;
// cout << representante << ": \n";
get_punto_medio();
}
};
int N;
vector<int>parent;
vector<componente> arboles;
vector<vector<int>> miembros_de_componente;
dsu(int n)
{
parent.resize(n);
N = n;
miembros_de_componente.resize(n);
for (int i = 0; i < N; i++)
parent[i] = i;
}
void une (int a, int b)
{
parent[busca(a)] = busca(b);
}
int busca (int a)
{
if (parent[a] == a) return a;
return (parent[a] = busca(parent[a]));
}
void crea_componentes()
{
for (int i = 0; i < N; i++)
miembros_de_componente[busca(i)].push_back(i);
for (int i = 0; i < N; i++)
{
if (miembros_de_componente[i].empty()) continue;
componente comp_temp;
comp_temp.representante = i;
comp_temp.miembros = miembros_de_componente[i];
arboles.push_back(comp_temp);
arboles.back().get_diametro();
//cout << '\n';
}
}
};
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
// cout << '\n';
max_tam = N;
adj.resize(N);
edge temp_edge;
dsu bosque(N);
for (int i = 0; i < M; i++)
{
temp_edge.u = B[i];
temp_edge.w = T[i];
adj[A[i]].push_back(temp_edge);
temp_edge.u = A[i];
adj[B[i]].push_back(temp_edge);
bosque.une(A[i], B[i]);
}
bosque.crea_componentes();
int temp_mid_pnt;
int cnt = 1;
vector<dsu::componente> vector_componentes;
for (dsu::componente comp: bosque.arboles)
vector_componentes.push_back(comp);
for (int i = 1; i < vector_componentes.size(); i++)
{
dsu::componente comp = vector_componentes[i], sig = vector_componentes[i-1];
adj[comp.punto_medio].push_back({sig.punto_medio, L});
adj[sig.punto_medio].push_back({comp.punto_medio, L});
bosque.une(comp.punto_medio, sig.punto_medio);
int temp_int = min (max (comp.distancia_punto_medio+L, sig.distancia_punto_medio+L), max(comp.distancia_punto_medio, sig.distancia_punto_medio+L));
vector_componentes[i].distancia_punto_medio = temp_int;
vector_componentes[i].diametro = max (comp.diametro, max (sig.diametro, comp.distancia_punto_medio + sig.distancia_punto_medio + L));
}
// bosque.crea_componentes();
return vector_componentes.back().distancia_punto_medio;
}
Compilation message
dreaming.cpp: In member function 'void dsu::componente::get_punto_medio()':
dreaming.cpp:111:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < miembros.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:202:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<dsu::componente>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
202 | for (int i = 1; i < vector_componentes.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:196:9: warning: unused variable 'temp_mid_pnt' [-Wunused-variable]
196 | int temp_mid_pnt;
| ^~~~~~~~~~~~
dreaming.cpp:197:9: warning: unused variable 'cnt' [-Wunused-variable]
197 | int cnt = 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
36456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
36456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
51036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
36456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
