| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1285414 | sundryyarn | 꿈 (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
// #include "dreaming.h"
#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
typedef pair<int, int> pi;
inline pair<int, vector<int>> getTreeDiameters(const vector<vector<pi>>& g)
{
const int N = g.size();
vector<bool> visited(N, false);
const auto getFurthest = [&](const int start, vector<int>& dist) -> int
{
int result = start;
queue<int> q({start});
visited[start] = true;
while (! q.empty())
{
const int u = q.front();
q.pop();
for (const pi& p : g[u])
if (! visited[p.second])
{
q.push(p.second);
visited[p.second] = true;
dist[p.second] = dist[u] + p.first;
// cout << u << " -> " << p.second << ", dist " << dist[u] << " -> " << dist[p.second] << endl;
if (dist[result] < dist[p.second])
result = p.second;
}
}
return result;
};
const auto getMinDist = [&](const int start, const vector<int>& du, const vector<int>& dv) -> int
{
int result = max(du[start], dv[start]);
queue<int> q({start});
visited[start] = true;
while (! q.empty())
{
const int u = q.front();
q.pop();
for (const pi& p : g[u])
if (! visited[p.second])
{
q.push(p.second);
visited[p.second] = true;
result = min(result, max(du[p.second], dv[p.second]));
}
}
return result;
};
vector<int> tree_u, tree_v, d_(N, 0), du(N, 0), dv(N, 0);
for (int i = 0; i < N; i ++)
if (! visited[i])
tree_u.push_back(getFurthest(i, d_));
// cout << "distances from u:\n";
visited = vector<bool>(N, 0);
for (const int& u : tree_u)
tree_v.push_back(getFurthest(u, du));
int internal = *max_element(du.begin(), du.end());
vector<int> result;
if (tree_u.size() == 1) return make_pair(internal, result);
// cout << "distances from v:\n";
visited = vector<bool>(N, 0);
for (const int& v : tree_v)
getFurthest(v, dv);
visited = vector<bool>(N, 0);
for (const int& u : tree_u)
result.push_back(getMinDist(u, du, dv));
sort(result.rbegin(), result.rend());
return make_pair(internal, result);
}
inline int getArrangedTime(const vector<int>& tree, const int& L)
{
// cout << "tree: ";
// for (const int& p : tree) cout << p << " ";
// cout << endl;
int u = 0, v = 1, N = tree.size(), p[N], left = 100000, right = 100002;
p[0] = 100001;
p[1] = 100002;
const auto distance = [&](const int& a, const int& b, const int& pa, const int& pb) -> int { return tree[a] + tree[b] + L * abs(pa - pb); };
int cur = distance(u, v, p[u], p[v]);
for (int i = 2; i < tree.size(); i ++)
{
const int left_dist = max(distance(u, i, p[u], left), distance(v, i, p[v], left)),
right_dist = max(distance(u, i, p[u], right), distance(v, i, p[v], right));
if (left_dist < right_dist)
{
p[i] = left --;
cur = max(cur, left_dist);
}
else
{
p[i] = right ++;
cur = max(cur, right_dist);
}
}
return cur;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
vector<vector<pi>> g(N);
for (int i = 0; i < M; i ++)
{
g[A[i]].push_back(make_pair(T[i], B[i]));
g[B[i]].push_back(make_pair(T[i], A[i]));
}
int internal;
vector<int> tree;
tie(internal, tree) = getTreeDiameters(g);
if (tree.empty()) return internal;
return max(internal, getArrangedTime(tree, L));
}
// int main()
// {
// freopen("dreaming.in", "r", stdin);
// freopen("dreaming.out", "w", stdout);
// int N, M, L;
// cin >> N >> M >> L;
// int A[M], B[M], T[M];
// for (int i = 0; i < M; i ++)
// cin >> A[i] >> B[i] >> T[i];
// cout << travelTime(N, M, L, A, B, T);
// return 0;
// }