Submission #1271507

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

dreaming

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, ll>;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    // Build adjacency list with existing trails
    vector<vector<pii>> 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]}); // Undirected graph
    }

    // Find connected components and their diameters
    vector<ll> group_ans, diameters;
    vector<bool> visited(N, false);
    for (int i = 0; i < N; i++) {
        if (visited[i]) continue;
        vector<int> group;
        queue<int> qq;
        qq.push(i);
        visited[i] = true;
        while (!qq.empty()) {
            int u = qq.front(); qq.pop();
            group.push_back(u);
            for (auto [v, w] : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    qq.push(v);
                }
            }
        }

        // Function to find the minimum maximum distance in a component
        auto f = [&](const vector<int>& comp) {
            if (comp.empty()) return 0LL;
            int start = comp[0];
            // Find farthest node a from start
            vector<bool> vis(N, false);
            ll mx_dist = 0;
            int a = -1;
            queue<pair<int, ll>> q;
            q.push({start, 0LL});
            while (!q.empty()) {
                auto [u, d] = q.front(); q.pop();
                if (vis[u]) continue;
                vis[u] = true;
                if (d > mx_dist) {
                    mx_dist = d;
                    a = u;
                }
                for (auto [v, w] : adj[u]) {
                    if (!vis[v]) q.push({v, d + w});
                }
            }
            // From a, compute d1 and find b
            vector<ll> d1(N, -1LL);
            vector<bool> vis2(N, false);
            queue<pair<int, ll>> q2;
            q2.push({a, 0LL});
            ll mx2 = 0;
            int b = -1;
            while (!q2.empty()) {
                auto [u, d] = q2.front(); q2.pop();
                if (vis2[u]) continue;
                vis2[u] = true;
                d1[u] = d;
                if (d > mx2) {
                    mx2 = d;
                    b = u;
                }
                for (auto [v, w] : adj[u]) {
                    if (!vis2[v]) q2.push({v, d + w});
                }
            }
            // From b, compute d2
            vector<ll> d2(N, -1LL);
            vector<bool> vis3(N, false);
            queue<pair<int, ll>> q3;
            q3.push({b, 0LL});
            while (!q3.empty()) {
                auto [u, d] = q3.front(); q3.pop();
                if (vis3[u]) continue;
                vis3[u] = true;
                d2[u] = d;
                for (auto [v, w] : adj[u]) {
                    if (!vis3[v]) q3.push({v, d + w});
                }
            }
            diameters.push_back(d1[b]);
            ll ans = LLONG_MAX;
            for (int i : comp) {
                if (d1[i] != -1 && d2[i] != -1) {
                    ans = min(ans, max(d1[i], d2[i]));
                }
            }
            return ans;
        };

        group_ans.push_back(f(group));
    }

    // Sort diameters in descending order
    sort(group_ans.rbegin(), group_ans.rend());
    ll res = 0;
    size_t k = group_ans.size();
    if (k >= 1) res = max(res, group_ans[0]);
    if (k >= 2) res = max(res, group_ans[0] + group_ans[1] + L); // L is the new trail length
    if (k >= 3) res = max(res, group_ans[1] + group_ans[2] + 2 * L);
    for (auto d : diameters) {
        res = max(res, d);
    }

    // Ensure the result fits in int (problem constraints guarantee this)
    return (int)min(res, (ll)INT_MAX);
}

Compilation message (stderr)

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