| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 741592 | MODDI | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dreaming.h"
#include <bits/stdc++.>
using namespace std;
vector<pair<int,long long> > G[100100];
bool vis[100100];
long long distance[100100][2];
int center = -1, path = -1;
set<pair<int,long long> > c;
pair<int, long long > dfs(int at, long long dist, int id){
pair<int, long long> rez = make_pair(at, dist);
distance[at][id] = dist;
if(path != -1){
if(distance[at][0] + dist == path){
c.insert(make_pair(at, max(distance[at][0], dist)));
}
}
for(auto next : G[at]){
if(!vis[next.first]){
pair<int, long long> cur = dfs(next.first, dist + next.second, id);
if(cur.second > rez.second){
rez = cur;
}
}
}
return rez;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(vis, false, sizeof vis);
for(int i = 0; i < M; i++){
G[A[i]].pb(mp(B[i], T[i]));
G[B[i]].pb(mp(A[i], T[i]));
}
vector<pair<int, long long> > arr;
for(int i = 0; i < N; i++){
if(vis[i]) continue;
else{
c.clear();
pair<int, long long> a = dfs(0, 0);
pair<int, long long> b = dfs(a.first, 0); // a i b kraevi na diameter
path = b.second;
pair<int, long long> s = dfs(a.first, 0);
arr.pb(*c.begin());
}
}
sort(arr.rbegin(), arr.rend());
int ans = arr[0].second + arr[1].second + L;
return ans;
}