Submission #508769

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

dreaming

#include "bits/stdc++.h"
// #include "dreaming.h"
using namespace std;

const int maxn=1e5+5;
int idx,jog,ans;
int dp[maxn][2];
bool vis[maxn];
vector<pair<int,int>>E[maxn];

void calc(int nd,int pr){
    vis[nd] = 1;
    int a = 0,b = 0;
    for(auto i : E[nd]){
        if(i.first == pr) continue;
        calc(i.first,nd);
        if(dp[i.first][0] + i.second > a) b=a,a = dp[i.first][0] + i.second;
        else if(dp[i.first][0] + i.second > b) b=dp[i.first][0] + i.second;
    }
    dp[nd][0] = a;
    dp[nd][1] = b;
    ans = max(ans,a + b);
}

void dfs(int nd,int pr,int yok){
    vis[nd] = 1;
    if(max(yok,dp[nd][0]) < jog){
        idx = nd;
        jog = max(yok,dp[nd][0]);
    }
    for(auto i : E[nd]){
        if(i.first == pr) continue;
        if(dp[i.first][0] + i.second == dp[nd][0]) dfs(i.first,nd,max(yok,dp[nd][1])+i.second);
        else dfs(i.first,nd,max(yok,dp[nd][0])+i.second);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0;i < M;i++){
        E[A[i]].push_back({B[i],T[i]});
        E[B[i]].push_back({A[i],T[i]});
    }
    for(int i = 0;i < N;i++) if(!vis[i]) calc(i,0);
    memset(vis,0,sizeof(vis));
    vector<pair<int,int>>v;
    for(int i = 0;i < N;i++){
        if(vis[i]) continue;
        idx = -1;
        jog = 2e9;
        dfs(i,-1,0);
        v.push_back({jog,idx});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    if(M != N-1) ans = max({ans,v[0].first + v[1].first + L});
    if((int)v.size() >= 3) ans = max(ans,v[1].first+v[2].first + 2*L);
    return ans;
}

int main(){
    int n,m,l; cin >> n >> m >> l;
    int a[m],b[m],t[m];
    for(int i = 0;i < m;i++) cin >> a[i] >> b[i] >> t[i];
    cout<<travelTime(n,m,l,a,b,t);
}

Compilation message (stderr)

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