Submission #806993

#	Time	Username	Problem	Language	Result	Execution time	Memory
806993		jakobrs	Dreaming (IOI13_dreaming)	C++17	100 / 100	74 ms	31356 KiB

dreaming

#include <algorithm>
#include <iostream>
#include <vector>

#include "dreaming.h"

void calculateDepths(const std::vector<std::vector<std::pair<int, int>>> &adj,
                     std::vector<int> &component, std::vector<int> &depths,
                     int node, int parent) {
    component.push_back(node);
    int depth = 0;
    for (auto [n, l] : adj[node]) {
        if (n == parent) continue;
        calculateDepths(adj, component, depths, n, node);
        depth = std::max(depth, l + depths[n]);
    }
    depths[node] = depth;
}
void calculateEccentricities(
    const std::vector<std::vector<std::pair<int, int>>> &adj,
    std::vector<int> &depths, std::vector<int> &eccentricities, int &diameter,
    int up, int node, int parent) {
    int down = up;
    int second_down = 0;
    int c = 0;
    for (auto [n, l] : adj[node]) {
        if (n == parent) continue;
        c += 1;
        int q = l + depths[n];
        if (q > down) {
            second_down = down;
            down = q;
        } else if (q > second_down) {
            second_down = q;
        }
    }
    eccentricities[node] = down;
    diameter = std::max(diameter, down + second_down);

    std::vector<int> suffixes(adj[node].size() + 1);
    suffixes.push_back(0);
    for (int i = adj[node].size() - 1; i > 0; i--) {
        auto [n, l] = adj[node][i];
        if (n == parent)
            suffixes.push_back(std::max(suffixes.back(), up));
        else
            suffixes.push_back(std::max(suffixes.back(), l + depths[n]));
    }
    std::reverse(suffixes.begin(), suffixes.end());

    int prefix = 0;
    for (int i = 0; i < adj[node].size(); i++) {
        auto [n, l] = adj[node][i];
        if (n == parent) {
            prefix = std::max(prefix, up);
        } else {
            calculateEccentricities(adj, depths, eccentricities, diameter,
                                    std::max(prefix, suffixes[i]) + l, n, node);
            prefix = std::max(prefix, l + depths[n]);
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    std::vector<std::vector<std::pair<int, int>>> adj(N);

    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }

    std::vector<bool> visited(N, false);
    std::vector<int> depths(N), eccentricities(N);
    std::vector<int> component;
    std::vector<int> q;
    int internal_worst = 0;
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            component.clear();
            calculateDepths(adj, component, depths, i, -1);
            int diameter = 0;
            calculateEccentricities(adj, depths, eccentricities, diameter, 0, i,
                                    -1);
            internal_worst = std::max(internal_worst, diameter);

            int centre = i;
            int eccentricity = eccentricities[i];

            for (int n : component) {
                visited[n] = true;
                if (eccentricities[n] < eccentricity) {
                    eccentricity = eccentricities[n];
                    centre = n;
                }
            }

            q.push_back(eccentricity);
        }
    }

    std::sort(q.begin(), q.end(), std::greater<int>{});
    if (q.size() == 1) {
        return internal_worst;
    } else if (q.size() == 2) {
        return std::max(internal_worst, q[0] + q[1] + L);
    } else {
        return std::max(internal_worst,
                        std::max(q[0] + q[1] + L, q[1] + q[2] + 2 * L));
    }
}

Compilation message (stderr)

dreaming.cpp: In function 'void calculateEccentricities(const std::vector<std::vector<std::pair<int, int> > >&, std::vector<int>&, std::vector<int>&, int&, int, int, int)':
dreaming.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < adj[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:86:17: warning: variable 'centre' set but not used [-Wunused-but-set-variable]
   86 |             int centre = i;
      |                 ^~~~~~

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