Submission #448454

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448454	2021-07-30T08:24:28 Z	NDT	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int n, m, DFSTime, CC;
int imax[4][N], belong[N], cntCC;
ll res, R[N], l, dist[4][N], maxdist;
vector<pii> adj[N];

void DFS(int u, int p)
{
    for (pii e : adj[u]) {
        int v = e.fi, w = e.se;
        if (DFSTime == 0) belong[v] = CC;
        if (v == p) continue;
        dist[DFSTime][v] = dist[DFSTime][u] + w;
        if (dist[DFSTime][v] > maxdist) {
            maxdist = dist[DFSTime][v];
            imax[DFSTime][cntCC] = v;
        }
        DFS(v, u);
    }
}

void solve()
{
    sort(R + 1, R + CC + 1, greater<ll>());
    // 1 bridge
    if (CC >= 2) res = max(res, R[1] + R[2] + l);
    // 2 bridge
    if (CC >= 3) res = max(res, R[2] + R[3] + l * 2);
    cout << res << '\n';
}

int main()
{
#ifdef NDT
    freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> l;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i = 0; i < n; ++i) {
        if (dist[DFSTime][i]) continue;
        cntCC = ++CC;
        imax[DFSTime][cntCC] = i;
        belong[i] = CC;
        maxdist = 0;
        DFS(i, i);
    }
    ++DFSTime;
    for (int i = 1; i <= CC; ++i) {
        maxdist = 0;
        cntCC = i;
        imax[DFSTime][cntCC] = i;
        DFS(imax[DFSTime - 1][i], imax[DFSTime - 1][i]);
        res = max(res, maxdist);
    }
    ++DFSTime;
    for (int i = 1; i <= CC; ++i) {
        maxdist = 0;
        cntCC = i;
        imax[DFSTime][cntCC] = i;
        DFS(imax[DFSTime - 1][i], imax[DFSTime - 1][i]);
    }
    for (int i = 1; i <= CC; ++i) R[i] = 1e15;
    for (int i = 0; i < n; ++i) {
        R[belong[i]] = min(R[belong[i]], max(dist[1][i], dist[2][i]));
    }
    solve();
    return 0;
}

Compilation message

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