Submission #1285415

#TimeUsernameProblemLanguageResultExecution timeMemory
1285415sundryyarnDreaming (IOI13_dreaming)C++17
47 / 100
120 ms8976 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;
// }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...