Submission #1269625

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

dreaming

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;

static vector<vector<pair<int,ll>>> adj;

pair<int,ll> farthest(int start, vector<ll>& dist, const vector<int>& comp) {
    // BFS/DFS works too since each comp is a tree, but Dijkstra is safe
    unordered_set<int> inComp(comp.begin(), comp.end());
    dist.assign(adj.size(), INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[start] = 0;
    pq.push({0,start});
    while(!pq.empty()) {
        auto [d,u] = pq.top(); pq.pop();
        if(d != dist[u]) continue;
        for(auto [v,w]: adj[u]) {
            if(!inComp.count(v)) continue;
            if(dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    int bestNode = start;
    ll bestDist = -1;
    for(int v: comp) {
        if(dist[v] < INF && dist[v] > bestDist) {
            bestDist = dist[v];
            bestNode = v;
        }
    }
    return {bestNode, bestDist};
}

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

    vector<int> seen(N,0);
    vector<ll> radii;
    ll maxDiam = 0;
    vector<ll> distA, distB;

    for(int i=0;i<N;i++) if(!seen[i]){
        // collect component
        vector<int> comp;
        stack<int> st;
        st.push(i); seen[i]=1;
        while(!st.empty()){
            int u=st.top(); st.pop();
            comp.push_back(u);
            for(auto [v,_]: adj[u]) if(!seen[v]){ seen[v]=1; st.push(v);}
        }

        // diameter endpoints
        auto [a,_1] = farthest(comp[0], distA, comp);
        auto [b,diam] = farthest(a, distA, comp);
        maxDiam = max(maxDiam, diam);

        // compute radius
        farthest(a, distA, comp);
        farthest(b, distB, comp);
        ll radius = INF;
        for(int v: comp){
            radius = min(radius, max(distA[v], distB[v]));
        }
        radii.push_back(radius);
    }

    sort(radii.begin(), radii.end(), greater<ll>());

    ll ans = maxDiam;
    if(radii.size() == 1){
        // nothing
    } else if(radii.size() == 2){
        ans = max(ans, radii[0] + radii[1] + L);
    } else {
        ans = max(ans, radii[0] + radii[1] + L);
        ans = max(ans, radii[1] + radii[2] + 2*L);
    }

    return ans;
}

Compilation message (stderr)

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