| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1358783 | Charizard2021 | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int> > > adj;
vector<bool> visited;
vector<long long> res;
long long dfs(int u, int p){
long long ans = 0;
for(pair<int, int> x : adj[u]){
int v = x.first;
if(v != p){
ans = max(ans, dfs(v, u) + x.second);
}
}
return ans;
}
long long dfs2(int u, int p){
visited[u] = true;
long long ans = res[u];
for(pair<int, int> x : adj[u]){
int v = x.first;
if(v != p){
ans = max(ans, dfs2(v, u));
}
}
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
adj.resize(N);
visited.resize(N);
res.resize(N);
for(int i = 0; i < M; i++){
adj[A[i]].push_back(make_pair(B[i], T[i]));
adj[B[i]].push_back(make_pair(A[i], T[i]));
}
for(int i = 0; i < N; i++){
res[i] = dfs(i, 0);
}
vector<long long> thing;
for(int i = 0; i < n; i++){
if(!visited[i]){
thing.push_back(dfs2(i, 0));
}
}
sort(thing.begin(), thing.end());
reverse(thing.begin(), thing.end());
if((int)thing.size() > 1){
return thing[0] + thing[1] + L;
}
else{
return 0;
}
}
