Submission #1271504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271504		nexus77	Dreaming (IOI13_dreaming)	C++20	Compilation error	0 ms	0 KiB

dreaming

#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

using ll = long long;

// Adjacency list: stores pairs of {neighbor_node, edge_weight}
static vector<vector<pair<int, int>>> adj;

// Global storage for calculated radii and diameters of each component
static vector<ll> radii;
static vector<ll> diameters;

pair<int, ll> bfs(int start_node, int n, vector<ll>& distances) {
    fill(distances.begin(), distances.end(), -1);
    queue<pair<int, ll>> q;

    distances[start_node] = 0;
    q.push({start_node, 0});

    int farthest_node = start_node;
    ll max_dist = 0;

    while (!q.empty()) {
        auto [u, d] = q.front();
        q.pop();

        if (d > max_dist) {
            max_dist = d;
            farthest_node = u;
        }

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (distances[v] == -1) { 
                distances[v] = d + w;
                q.push({v, distances[v]});
            }
        }
    }
    return {farthest_node, max_dist};
}

void analyze_component(const vector<int>& component_nodes, int n) {
    if (component_nodes.empty()) return;

    vector<ll> temp_distances(n);
    auto [a, dist_a] = bfs(component_nodes[0], n, temp_distances);

    vector<ll> d1(n);
    auto [b, diameter] = bfs(a, n, d1);
    diameters.push_back(diameter);

    vector<ll> d2(n);
    bfs(b, n, d2);

    ll component_radius = -1;
    for (int node : component_nodes) {
        ll eccentricity = max(d1[node], d2[node]);
        if (component_radius == -1 || eccentricity < component_radius) {
            component_radius = eccentricity;
        }
    }
    radii.push_back(component_radius);
}

void find_component(int u, vector<bool>& visited, vector<int>& component_nodes) {
    visited[u] = true;
    component_nodes.push_back(u);
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (!visited[v]) {
            find_component(v, visited, component_nodes);
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    adj.assign(N, {});
    radii.clear();
    diameters.clear();

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

    vector<bool> visited(N, false);
    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            vector<int> component_nodes;
            find_component(i, visited, component_nodes);
            analyze_component(component_nodes, N);
        }
    }

    sort(radii.rbegin(), radii.rend());

    ll max_diameter = 0;
    if (!diameters.empty()) {
        max_diameter = *max_element(diameters.begin(), diameters.end());
    }

    ll result = max_diameter;

    if (radii.size() >= 2) {
        result = max(result, radii[0] + radii[1] + L);
    }

    if (radii.size() >= 3) {
        result = max(result, radii[1] + radii[2] + 2LL * L);
    }

    return (int)result;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccSwtVHJ.o: in function `main':
grader.c:(.text.startup+0xc5): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status