Submission #1101815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101815		totoro	Dreaming (IOI13_dreaming)	C++17	47 / 100	1063 ms	13380 KiB

dreaming

// UNSOLVED SUBTASK 1 (14 pts)
// UNSOLVED SUBTASK 2 (10 pts)
// UNSOLVED SUBTASK 3 (23 pts)
// UNSOLVED SUBTASK 4 (18 pts)
// UNSOLVED SUBTASK 5 (12 pts)
// UNSOLVED SUBTASK 6 (23 pts)
// [+-+]----------------------
// TOTAL      0/100 pts

#include "dreaming.h"

#include <algorithm>
#include <queue>
#include <vector>

struct Edge {
    int from;
    int to;
    int length;
    Edge(int from, int to, int length) : from(from), to(to), length(length) {}
    bool operator<(const Edge& other) {
        return from < other.from;
    }
};
bool operator<(const Edge& a, const Edge& b) {
    return a.from < b.from;
}

int farthest_node(const std::vector<std::vector<Edge>>& tree, int a) {
    std::vector<bool> visited(tree.size());
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
    q.emplace(0, a);
    int last;
    while (!q.empty()) {
        auto el = q.top();
        q.pop();
        if (visited[el.second]) continue;
        visited[el.second] = true;
        for (auto edge : tree[el.second]) {
            q.emplace(el.first + edge.length, edge.to);
        }
        last = el.second;
    }
    return last;
}

std::vector<Edge> dijkstra_path(const std::vector<std::vector<Edge>>& tree, int a, int b) {
    std::vector<bool> visited(tree.size());
    std::priority_queue<std::pair<int, std::pair<Edge, int>>> q;
    Edge dummy = Edge(-1, a, -1);
    q.emplace(0, std::pair<Edge, int>(dummy, a));
    std::vector<Edge> from(tree.size(), dummy);
    while (!q.empty() && q.top().second.second != b) {
        auto el = q.top();
        q.pop();
        if (visited[el.second.second]) continue;
        visited[el.second.second] = true;
        from[el.second.second] = el.second.first;
        for (auto edge : tree[el.second.second]) {
            q.emplace(el.first + edge.length, std::pair<Edge, int>(edge, edge.to));
        }
    }
    if (q.empty()) return {};
    from[b] = q.top().second.first;
    std::vector<Edge> path;
    int current = b;
    while (current != a) {
        path.push_back(from[current]);
        current = from[current].from;
    }
    return path;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    std::vector<std::vector<Edge>> tree(N);
    for (int i = 0; i < M; ++i) {
        tree[A[i]].emplace_back(A[i], B[i], T[i]);
        tree[B[i]].emplace_back(B[i], A[i], T[i]);
    }
    // floodfill
    std::vector<int> color(N);
    std::vector<int> parents;
    int current = 1;
    for (int i = 0; i < N; ++i) {
        if (color[i]) continue;
        parents.push_back(i);
        std::vector<int> stack;
        stack.push_back(i);
        while (!stack.empty()) {
            int back = stack.back();
            stack.pop_back();
            if (color[back]) continue;
            color[back] = current;
            for (auto edge : tree[back]) {
                stack.push_back(edge.to);
            }
        }
        ++current;
    }

    // radius and centers
    std::vector<std::pair<int, int>> radius_centers(parents.size());
    int sp = 0;
    int largest_diameter = 0;
    for (auto parent : parents) {
        int b = farthest_node(tree, parent);
        int a = farthest_node(tree, b);
        if (a == b) {
            radius_centers[sp++] = std::make_pair(0, parent);
            continue;
        }
        auto diameter = dijkstra_path(tree, b, a);
        int sum = 0;
        for (auto edge : diameter) {
            sum += edge.length;
        }
        largest_diameter = std::max(largest_diameter, sum);
        int small_sum = 0;
        int i = 0;
        while (i < diameter.size() && small_sum <= sum / 2) {
            small_sum += diameter[i++].length;
        }
        if (sum - small_sum + diameter[i - 1].length < small_sum) {
            --i;
            small_sum = sum - small_sum + diameter[i].length;
        }
        radius_centers[sp++] = std::make_pair(small_sum, i > 0 ? diameter[i - 1].from : diameter[i].to);
    }

    if (radius_centers.size() < 2) {
        return largest_diameter;
    }
    std::sort(radius_centers.rbegin(), radius_centers.rend());
    return std::max(largest_diameter, radius_centers[0].first + L + radius_centers[1].first);
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         while (i < diameter.size() && small_sum <= sum / 2) {
      |                ~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int farthest_node(const std::vector<std::vector<Edge> >&, int)':
dreaming.cpp:44:12: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     return last;
      |            ^~~~

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