# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1266016 | cordeiroalone | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
using ll = long long;
vector<pair<ll,int>> listaadj[MAX];
bool calculado[MAX];
vector<int> centros;
int filhos[MAX];
ll distancias[MAX];
ll distlegal[MAX][2];
vector<int> arvoreatual;
void contaarvore(int x,int pai){
arvoreatual.push_back(x);
calculado[x] = 1;
for(auto v : listaadj[x]){
if(v.second == pai) continue;
contaarvore(v.second,x);
}
}
void dfs(int x,int pai,int modo){
for(auto v : listaadj[x]){
if(v.second == pai) continue;
distlegal[v.second][modo] = distlegal[x][modo] + v.first;
dfs(v.second,x,modo);
}
}
void calcularcentro(int x){
distlegal[x][0] = 0;
contaarvore(x,0);
dfs(x,0,0);
ll maiordist = 0,maiorid;
for(auto v : arvoreatual){
if(distlegal[v][0] > maiordist){
maiordist = distlegal[v][0];
maiorid = v;
}
}
distlegal[maiorid][0] = 0;
dfs(maiorid,0,0);
ll maiordist2 = 0,maiorid2;
for(auto v : arvoreatual){
if(distlegal[v][0] > maiordist2){
maiordist2 = distlegal[v][0];
maiorid2 = v;
}
}
distlegal[maiorid2][1] = 0;
dfs(maiorid2,0,1);
ll menortotal = INT64_MAX;
for(auto v : arvoreatual){
menortotal = min(menortotal,max(distlegal[v][0],distlegal[v][1]));
}
vector<int> temp;
swap(temp,arvoreatual);
centros.push_back(menortotal);
}
int main(void){
int n,m,l; cin >> n >> m >> l;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i = 0; i < M; i++){
int a = A[0],b = B[0],w = T[0];
listaadj[a].push_back({w,b});
listaadj[b].push_back({w,a});
}
for(int i = 1; i <= N; i++){
if(calculado[i])continue;
calcularcentro(i);
}
sort(centros.begin(),centros.end());
if(centros.size() == 1){
return(centros[0]);
}else{
return(centros[centros.size() - 1] + centros[centros.size() - 2] + L);
}
}