| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 661295 | atigun | Dreaming (IOI13_dreaming) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;
typedef long long ll;
const int maxn = 1e5;
vector<vector<pair<int, int>>> g(maxn+5);
vector<bool> vis(maxn+5, false);
vector<int> dt(maxn+5), ht(maxn+5, 0), group(maxn+5);
vector<multiset<int>> S(maxn+5);
void dfs1(int v, int P){
group[v] = P;
vis[v] = 1;
int maxi1 = 0, maxi2 = 0;
for(pair<int, int> pp : g[v]){
int u = pp.first, w = pp.second;
if(vis[u])
continue;
dfs1(u, P);
ht[v] = max(ht[v], ht[u]+w);
if(ht[u]+w >= maxi1){
maxi2 = maxi1, maxi1 = ht[u]+w;
} else if(ht[u]+w >= maxi2){
maxi2 = ht[u]+w;
}
}
dt[v] = maxi1+maxi2;
}
void dfs2(int v, int p){
vis[v] = 1;
for(pair<int, int> pp : g[v]){
int u = pp.first, w = pp.second;
if(u == p)
continue;
S[v].insert(ht[u]+w);
}
for(pair<int, int> pp : g[v]){
int u = pp.first, w = pp.second;
if(u == p)
continue;
if(S[v].size() == 1){
S[u].insert(w);
} else if(!S[v].empty()){
S[v].erase(S[v].find(ht[u]+w));
int best = *--S[v].end();
S[u].insert(best+w);
S[v].insert(ht[u]+w);
}
}
if(!S[v].empty())
ht[v] = *--S[v].end();
for(pair<int, int> pp : g[v]){
int u = pp.first;
if(vis[u])
continue;
dfs2(u, v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for(int i = 0; i < M; i++){
g[A[i]].emplace_back(B[i], T[i]);
g[B[i]].emplace_back(A[i], T[i]);
}
for(int i = 0; i < N; i++)
if(!vis[i])
dfs1(i, i);
fill(vis.begin(), vis.end(), false);
for(int i = 0; i < N; i++)
if(!vis[i])
dfs2(i, -1);
long long ans = 0;
for(int i = 0; i < N; i++)
ans = max(ans, dt[i]);
vector<pair<int, int>> order;
order.reserve(N);
for(int i = 0; i < N; i++)
order.emplace_back(ht[i], group[i]);
sort(order.begin(), order.end());
vector<int> G;
G.reserve(N);
vector<bool> used(N+5, false);
for(int i = 0; i < N; i++){
if(used[order[i].second])
continue;
G.emplace_back(order[i].first);
used[order[i].second] = true;
}
int GN = G.size();
sort(G.begin(), G.end(), [&](int n1, int n2){
return n1 > n2;
});
for(int i = GN-1; i > 0; i--)
ans = max(ans, (long long) G[0] + (long long) G[i] + i*1ll*L);
return ans;
}