이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int travelTime(int N , int M , int L , int A[] , int B[] , int T[]){
vector<vector<int>> g(N + 1) , w(N + 1);
auto add_edge = [&](int u , int v , int weight){
g[u].emplace_back(v);
w[u].emplace_back(weight);
};
for(int i = 0;i < M;i ++){
++A[i],++B[i];
add_edge(A[i] , B[i] , T[i]);
add_edge(B[i] , A[i] , T[i]);
}
vector<int> visited(N + 1) , d(N + 1) , mx(N + 1) , non_sub(N + 1) , max_depths;
function<void(int , int)> dfs = [&](int u , int p){
for(int x = 0;x < (int)g[u].size();x ++){
if(g[u][x] != p){
d[g[u][x]] = d[u] + w[u][x];
dfs(g[u][x] , u);
mx[u] = max(mx[u] , mx[g[u][x]] + w[u][x]);
}
}
};
function<int(int)> DFS = [&](int u){
visited[u] = 1;
int mn = max(mx[u] , non_sub[u]);
multiset<int> X;
for(int x = 0;x < (int)g[u].size();x ++){
if(visited[g[u][x]] == 0){
X.insert(mx[g[u][x]] + w[u][x]);
}
}
for(int x = 0;x < (int)g[u].size();x ++){
if(visited[g[u][x]] == 0){
X.erase(X.find(mx[g[u][x]] + w[u][x]));
non_sub[g[u][x]] = max(non_sub[u] , (X.empty() ? 0 : *--X.end())) + w[u][x];
mn = min(mn , DFS(g[u][x]));
X.insert(mx[g[u][x]] + w[u][x]);
}
}
return mn;
};
for(int i = 1;i <= N;i ++){
if(visited[i] == 0){
dfs(i , -1);
max_depths.emplace_back(DFS(i));
}
}
int sz = max_depths.size();
sort(max_depths.begin() , max_depths.end());
if(sz == 2){
return max_depths[0] + max_depths[1] + L;
}
return max(max_depths[sz - 1] + max_depths[sz - 2] + L , max_depths[sz - 2] + max_depths[sz - 3] + 2 * L);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |