Submission #1301946

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

dreaming

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

#define fastio ios::sync_with_stdio(false); cin.tie(nullptr)
#define all(x) (x).begin(), (x).end()
using ll = long long;

struct Edge {
    int to;
    int w;
};

pair<int,ll> farthest(int src, const vector<vector<Edge>>& g, const vector<int>& comp, vector<ll>* outDist=nullptr) {
    // Tree distances via stack (no cycles inside component)
    unordered_set<int> inComp;
    inComp.reserve(comp.size()*2);
    for (int v: comp) inComp.insert(v);

    vector<ll> dist(g.size(), -1);
    vector<int> st;
    st.reserve(comp.size());
    st.push_back(src);
    dist[src] = 0;

    // iterative DFS with parent simulation
    vector<int> par(g.size(), -1);
    while (!st.empty()) {
        int v = st.back(); st.pop_back();
        for (auto e: g[v]) {
            if (!inComp.count(e.to)) continue;
            if (e.to == par[v]) continue;
            par[e.to] = v;
            dist[e.to] = dist[v] + e.w;
            st.push_back(e.to);
        }
    }

    int bestV = src;
    ll bestD = 0;
    for (int v: comp) {
        if (dist[v] > bestD) bestD = dist[v], bestV = v;
    }
    if (outDist) *outDist = std::move(dist);
    return {bestV, bestD};
}

int main() {
    fastio;

    int N, M;
    ll L;
    cin >> N >> M >> L;

    vector<vector<Edge>> g(N);
    for (int i = 0; i < M; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        g[a].push_back({b, t});
        g[b].push_back({a, t});
    }

    vector<int> vis(N, 0);
    vector<ll> radii;
    ll maxDiam = 0;

    for (int i = 0; i < N; i++) if (!vis[i]) {
        // collect component nodes
        vector<int> comp;
        comp.reserve(256);
        stack<int> st;
        st.push(i);
        vis[i] = 1;
        while (!st.empty()) {
            int v = st.top(); st.pop();
            comp.push_back(v);
            for (auto e: g[v]) if (!vis[e.to]) {
                vis[e.to] = 1;
                st.push(e.to);
            }
        }

        // diameter endpoints A, B
        auto A = farthest(comp[0], g, comp);
        vector<ll> distA, distB;
        auto B = farthest(A.first, g, comp, &distA);
        auto C = farthest(B.first, g, comp, &distB); // C.first == A.first, C.second == diameter
        ll diam = C.second;
        maxDiam = max(maxDiam, diam);

        // radius = min_v max(distA[v], distB[v])
        ll rad = (ll)4e18;
        for (int v: comp) {
            // distA/distB are size N, but only valid for nodes in this component
            ll ecc = max(distA[v], distB[v]);
            rad = min(rad, ecc);
        }
        radii.push_back(rad);
    }

    sort(all(radii), greater<ll>());

    ll ans = maxDiam;
    if ((int)radii.size() >= 2) ans = max(ans, radii[0] + L + radii[1]);
    if ((int)radii.size() >= 3) ans = max(ans, radii[1] + 2*L + radii[2]);

    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccYvJYri.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccI5bLYe.o:dreaming.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccYvJYri.o: in function `main':
grader.c:(.text.startup+0xc5): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status