| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 251275 | AaronNaidu | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
vector<pair<int, int>> graph[100001];
//int dists[100001];
bool visited[100001];
int maxDist = 0;
int maxNode = 0;
void dfs(int node, int parent, int dist) {
//dists[node] = distance;
if (dist > maxDist)
{
maxDist = dist;
maxNode = node;
}
for (auto i : graph[node])
{
if (i.first != parent)
{
dfs(i.first, node, dist + i.second);
}
}
visited[node] = true;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for (int i = 0; i < m; i++)
{
graph[a[i]].push_back({b[i],t[i]});
graph[b[i]].push_back({a[i], t[i]});
}
dfs(0, -1, 0);
//cout << "Done dfs1 landed on " << maxNode << "\n";
int dfsFrom = maxNode;
maxDist = 0;
maxNode = dfsFrom;
dfs(dfsFrom, -1, 0);
//cout << "Done dfs2 landed on " << maxNode << "\n";
int currDist = maxDist;
int prevCurrDist = currDist;
int currNode = maxNode;
while (float(currDist) > maxDist/float(2))
{
for (auto i : graph[currNode])
{
if (dists[i.first] < dists[currNode])
{
currNode = i.first;
prevCurrDist = currDist;
currDist = dists[currNode];
break;
}
}
}
//cout << "Cand dists are " << currDist << " " << prevCurrDist << " out of " << maxDist << "\n";
int ans1 = min(max(currDist, maxDist - currDist), max(prevCurrDist, maxDist - prevCurrDist));
int start2 = 0;
for (int i = 0; i < n; i++)
{
if (!visited[i])
{
//cout << "Starting from " << start2 << "\n";
break;
}
start2++;
}
maxDist = 0;
maxNode = start2;
dfs(start2, -1, 0);
//cout << "Done dfs3 landed on " << maxNode << "\n";
dfsFrom = maxNode;
maxDist = 0;
maxNode = dfsFrom;
dfs(dfsFrom, -1, 0);
//cout << "Done dfs4 landed on " << maxNode << "\n";
currDist = maxDist;
prevCurrDist = currDist;
currNode = maxNode;
while (float(currDist) > maxDist/float(2))
{
for (auto i : graph[currNode])
{
if (dists[i.first] < dists[currNode])
{
currNode = i.first;
prevCurrDist = currDist;
currDist = dists[currNode];
break;
}
}
}
//cout << "Cand dists are " << currDist << " " << prevCurrDist << " out of " << maxDist << "\n";
int ans2 = min(max(currDist, maxDist - currDist), max(prevCurrDist, maxDist - prevCurrDist));
//cout << "Ans 1 is " << ans1 << "\n";
//cout << "Ans 2 is " << ans2 << "\n";
return ans1 + ans2 + l;
}