Submission #1102807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102807		totoro	Dreaming (IOI13_dreaming)	C++17	100 / 100	151 ms	21528 KiB

dreaming

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

#include "dreaming.h"

#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

struct Edge {
    int from;
    int to;
    int length;
    Edge(int from, int to, int length) : from(from), to(to), length(length) {}
    Edge() : from(-1), to(-1), length(-1) {}
};
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::unordered_set<int> visited;
    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.count(el.second)) continue;
        visited.insert(el.second);
        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::unordered_set<int> visited;
    std::priority_queue<std::pair<int, Edge>> q;
    Edge dummy = Edge(-1, a, -1);
    q.emplace(0, dummy);
    std::unordered_map<int, Edge> from;
    while (!q.empty() && q.top().second.to != b) {
        auto el = q.top();
        q.pop();
        if (visited.count(el.second.to)) continue;
        visited.insert(el.second.to);
        from[el.second.to] = el.second;
        for (auto edge : tree[el.second.to]) {
            q.emplace(el.first + edge.length, edge);
        }
    }
    if (q.empty()) return {};
    from[b] = q.top().second;
    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]);
    }
    // std::cout << "finished init" << std::endl;
    // 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;
    }
    // std::cout << "finished floodfill" << std::endl;

    // radius and centers
    std::vector<int> radii(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) {
            radii[sp++] = 0;
            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) {
            small_sum = sum - small_sum + diameter[i - 1].length;
        }
        radii[sp++] = small_sum;
        // if (sp % 100 == 0) {
        //     std::cout << "finished " << sp << " rads" << std::endl;
        // }
    }
    // std::cout << "finished rads" << std::endl;

    if (radii.size() < 2) {
        return largest_diameter;
    }
    std::sort(radii.rbegin(), radii.rend());
    // std::cout << "finished sorting" << std::endl;
    long long max = std::max(largest_diameter, radii[0] + L + radii[1]);
    if (radii.size() > 2) {
        max = std::max(max, (long long)L + L + radii[1] + radii[2]);
    }
    return max;
}

Compilation message (stderr)

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

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