Submission #1285394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285394		sundryyarn	꿈 (IOI13_dreaming)	C++17	0 / 100	39 ms	7448 KiB

dreaming

#include "dreaming.h"
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pi;
inline 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 << "then for u, \n";
    visited = vector<bool>(N, 0);
    for (const int& u : tree_u)
        tree_v.push_back(getFurthest(u, du));
    
    if (tree_u.size() == 1) return {*max(du.begin(), du.end())};

    // cout << "then for v, \n";
    visited = vector<bool>(N, 0);
    for (const int& v : tree_v)
        getFurthest(v, dv);
    

    vector<int> result;
    visited = vector<bool>(N, 0);
    for (const int& u : tree_u)
        result.push_back(getMinDist(u, du, dv));
    sort(result.rbegin(), result.rend());
    return result;
}
inline int getArrangedTime(const vector<int>& tree, const int& L)
{
    cout << "tree: ";
    for (const int& p : tree) cout << p << " ";
    cout << endl;

    if (tree.size() == 1) return tree[0];
    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]));
    }
    return getArrangedTime(getTreeDiameters(g), L);
}
// int main()
// {
//     int N = 12, M = 8, L = 2,
//         A[8] = {0,8,2,5,5,1,1,10},
//         B[8] = {8,2,7,11,1,3,9,6},
//         C[8] = {4,2,4,3,7,1,5,3};
//     cout << travelTime(N, M, L, A, B, C);
//     return 0;
// }

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23