| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 920270 | 2024-02-02T11:34:17 Z | Arp | 꿈 (IOI13_dreaming) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;
using i64 = long long;
const int N = 1e5;
vector<pair<int,int>> adj[N];
i64 down[N],up[N];
bool vis[N];
i64 mini = 1e18;
void dfs(int u){
vis[u] = true;
vector<i64> all;
i64 maxi = -1e18;
for(auto [v,w] : adj[u]){
if(vis[v]) continue;
// cout << u << " " << v << '\n';
down[v] = down[u] + w;
dfs(v);
up[u] = max(up[u],up[v] + w);
}
for(auto [v,w] : adj[u]){
up[v] = max(up[v],maxi + w);
maxi = max(maxi,up[v] + w);
}
maxi = -1e18;
reverse(adj[u].begin(),adj[u].end());
for(auto [v,w] : adj[u]){
up[v] = max(up[v],maxi + w);
maxi = max(maxi,up[v] + w);
}
}
void dfs2(int u,int p){
for(auto [v,w] : adj[u]){
if(v == p) continue;
dfs2(v,u);
}
mini = min(mini,max(down[u],up[u]));
}
i64 travelTime(int N,int M,int L,int A[],int B[],int T[]){
for(int i = 0;i<N;i++){
up[i] = down[i] = 0;
vis[i] = false;
}
for(int i = 0;i<M;i++){
adj[A[i]].emplace_back(B[i],T[i]);
adj[B[i]].emplace_back(A[i],T[i]);
}
multiset<i64> ms;
vector<i64> com;
int cc = 0;
for(int i = 0;i<N;i++){
if(!vis[i] && adj[i].size() <= 1){
mini = 1e18;
dfs(i);
dfs2(i,-1);
ms.insert(mini);
com.push_back(mini);
cc ++;
}
}
assert(cc - 1 == N - M - 1);
if(cc <= 2){
i64 sum = 0;
while(ms.size() > 0){
sum += *ms.begin();
ms.erase(ms.begin());
}
return sum + (cc - 1) * L;
}
i64 ans = 1e18;
for(i64 c : com){
ms.erase(ms.find(c));
i64 maxi1 = *(--ms.end());
ms.erase(ms.find(maxi1));
i64 maxi2 = *(--ms.end());
ans = min(ans,max(maxi1 + maxi2 + 2 * L,maxi1 + c + L));
ms.insert(c);
ms.insert(maxi1);
ms.insert(maxi2);
}
return ans;
}