Submission #472137

#	Time	Username	Problem	Language	Result	Execution time	Memory
472137		longvu	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

/**
 *    author:  longvu
 *    created: 09/13/21 12:30:26
**/
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = numeric_limits<int>::max();
const int nax = (int)(100001);
const int mod = 1e9 + 7;

template<class X, class Y>
bool maximize(X& x, const Y y) {
    if (y > x) {x = y; return true;}
    return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
    if (y < x) {x = y; return true;}
    return false;
}

vector<pair<int, int>> adj[nax];
int ncomp = 0, compID[nax], f[nax], g[nax];
void dfsf(int u, int pa) {
    compID[u] = ncomp;
    for (auto v : adj[u]) {
        if (pa == v.first) {
            continue;
        }
        dfsf(v.first, u);
        maximize(f[u], v.second + f[v.first]);
    }
} 

void dfsg(int u, int pa) {
    pair<int, int> mx = {-INF, -INF};
    for (auto v : adj[u]) {
        if (pa == v.first) {
            continue;
        }
        if (v.second + f[v.first] > mx.first) {
            mx.second = mx.first;
            mx.first = v.second + f[v.first];
        } else {
            maximize(mx.second, v.second + f[v.first]);
        }
    }
    for (auto v : adj[u]) {
        if (pa == v.first) {
            continue;
        }
        g[v.first] = max({v.second, v.second + g[u], v.second + ((v.second + f[v.first] == mx.first) ? mx.second : mx.first)});
        dfsg(v.first, u);
    }
}

int memo[nax];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, l;
    cin >> n >> m >> l;
    for (int i = 1; i <= m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        u++; v++;
        adj[v].push_back({u, c});
        adj[u].push_back({v, c});
    }
    for (int i = 1; i <= n; ++i) {
        if (!compID[i]) {
            ncomp++;
            dfsf(i, -1);
            dfsg(i, -1);
        }
    }
    memset(memo, 0x3f, sizeof memo);
    for (int i = 1; i <= n; ++i) {
        minimize(memo[compID[i]], max(g[i], f[i]));
    }
    // for (int i = 1; i <= ncomp; ++i) {
    //     cout << memo[i] << " ";
    // }
    // cout << '\n';
    sort(1 + memo, 1 + ncomp + memo);
    if (ncomp <= 1) {
        cout << memo[1] << '\n';
        return 0;
    }
    int ans = memo[ncomp] + memo[1] + l;
    if (ncomp >= 3) {
        maximize(ans, memo[ncomp - 1] + memo[ncomp] + l);
        maximize(ans, l * 2 +  memo[1] + memo[ncomp - 1]);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

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