Submission #1271506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271506		nexus77	Dreaming (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>;

ll f(const vector<int>& comp, const vector<vector<pii>>& adj, vector<ll>& diameters, int n) {
    if (comp.empty()) return 0;
    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>> qq;
    qq.push({start, 0LL});
    while (!qq.empty()) {
        auto [u, d] = qq.front(); qq.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]) {
                qq.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;
}

int main() {
    int n, m;
    ll x;
    cin >> n >> m >> x;
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int l, r;
        ll w;
        cin >> l >> r >> w;
        adj[l].push_back({r, w});
        adj[r].push_back({l, w});
    }
    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);
                }
            }
        }
        group_ans.push_back(f(group, adj, diameters, n));
    }
    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] + x);
    if (k >= 3) res = max(res, group_ans[1] + group_ans[2] + 2 * x);
    for (auto d : diameters) {
        res = max(res, d);
    }
    cout << res << endl;
    return 0;
}

Compilation message (stderr)

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