Submission #773248

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

dreaming

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

#define ll long long
#define ii pair<int, int>
#define fi first
#define se second;

const int maxn = 1e5 + 5;

int n, m, l;
vector<ii> ke[maxn];
ll d[maxn];
int tplt;
int X[maxn], Y[maxn];
ll dis, C_node[maxn], l_path[maxn];
ll res;
int par[maxn];

void inp(){
    cin >> n >> m >> l;
    for(int i=0; i<m; i++){
        int x, y, w; cin >> x >> y >> w;
        ke[x].push_back({y, w});
        ke[y].push_back({x, w});
    }
}

void dfs(int u, int parent){
    for(auto it : ke[u]){
        int v = it.fi, w = it.se;
        if(v != parent){
            d[v] = d[u] + w;
            if(d[v] > dis){
                dis = d[v];
                X[tplt] = v;
            }
            dfs(v, u);
        }
    }
}

void DFS(int u, int i){
    for(auto it : ke[u]){
        int v = it.fi, w = it.se;
        if(v != par[u]){
            par[v] = u;
            d[v] = d[u] + w;
            if(d[v] > l_path[i]){
                l_path[i] = d[v];
                Y[i] = v;
            }
            DFS(v, i);
        }
    }
}

void solve(){
    for(int i=0; i<n; i++){
        if(!d[i]){
            dis = 0;
            tplt++;
            X[tplt] = i;
            dfs(i, i);
        }
    }
    memset(d, 0, sizeof(d));
    for(int i=1; i<=tplt; i++){
        if(!d[X[i]]){
            Y[i] = X[i];
            DFS(X[i], i);
        }
    }
//    for(int i=1; i<=tplt; i++){
//        cout << l_path[i] << "\n";
//    }
//    for(int i=1; i<=tplt; i++){
////        cout << C_node[i] << "\n";
//        cout << X[i] << " " << Y[i] << "\n";
//    }
//    cout << l_path[3] << " " << Y[3] << " " << d[Y[3]] << endl;
    memset(C_node, 70, sizeof(C_node));
    for(int i=1; i<=tplt; i++){
        C_node[i] = min(C_node[i], max(l_path[i] - d[Y[i]], d[Y[i]]));
        while(X[i] != Y[i]){
            C_node[i] = min(C_node[i], max(l_path[i] - d[Y[i]], d[Y[i]]));
            Y[i] = par[Y[i]];
        }
    }
//    for(int i=1; i<=tplt; i++){
//        cout << C_node[i] << "\n";
////        cout << X[i] << " " << Y[i] << "\n";
//    }

    sort(C_node+1, C_node+tplt+1, greater<int>());
    for(int i=1; i<=tplt; i++){
        res = max(res, l_path[i]);
    }
    if(tplt >= 2){
        res = max(res, C_node[1] + C_node[2] + l);
    }
    if(tplt >= 3){
        res = max(res, C_node[2] + C_node[3] + 2*l);
    }
    cout << res << "\n";
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    inp();
    solve();
    return 0;
}

Compilation message (stderr)

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