Submission #96185

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

dreaming

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

vector< pair<int, int> > Graph[100009];
vector< bool > v(100009, false);
vector< int > ans(100009);

int Maxi = 0;
int maxi = -1;

int Last = 0;

void DFS(int node, int last, int dist){
   // cout << node << ' ' << last << endl;
    if(dist > Maxi){
        Maxi = dist;
        Last = node;
    }
    v[node] = true;
    for(auto a : Graph[node]){
        if(a.first != last){
            DFS(a.first, node,dist+a.second);
        }
    }
}

vector<int> diste(100009);

int radius;

void Radius(int node, int last, int dist){
    diste[node] = max(diste[node], dist);
    for(auto a : Graph[node]){
        if(a.first != last){
            Radius(a.first, node, dist+a.second);
        }
    }
}

void R(int node, int last, int dist, int diam){
    if(diste[node] == diam/2){
        radius = diam/2;
        return;
    }
    if(diste[node] < diam/2){
        radius = min(max(diste[last], diam-diste[last]), max(diste[node], diam-diste[node]));
        return ;
    }
    for(auto a : Graph[node]){
        if(a.first != last){
            R(a.first, node, dist+a.second, diam);
        }
    }
}

int F(int a){
   // cout << a << endl;
    Maxi = -1;
    DFS(a,-1,0);
    int A = Last;
   // cout << A << endl;
    Maxi = -1;
    DFS(A,-1,0);
    //cout << A << ' ' << "Diameter " << Maxi << endl;
    maxi = max(Maxi, maxi);
    int B = Last;
    int diam = Maxi;
    //cout << "Between node " << A << " and " << B << ' ' << diam << endl;
    for(int i = 0; i < 100009; i++){
        diste[i] = -1;
    }
    Radius(A, -1,0);
    radius = 0;
    R(B,-1,0,diam);
    //cout << radius << endl;
    return radius;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++){
        Graph[A[i]].push_back(make_pair(B[i], T[i]));
        Graph[B[i]].push_back(make_pair(A[i], T[i]));
    }
    int t = 0;
    for(int i = 0; i < N; i++){
        if(!v[i]){
            ans[t++] = F(i);//FUNCTION
        }
    }
    sort(ans.begin(), ans.begin()+t);
    reverse(ans.begin(), ans.begin()+t);
    if(t > 1){
        maxi = max(maxi, ans[0]+ans[1]+L);
        if(t > 2){
            maxi = max(maxi, ans[1]+ans[2]+2*L);
        }
    }
    return maxi;
}

int main(){
    int n, m, l;
    cin >> n >> m >> l;
    int a[m];
    int b[m];
    int t[m];
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> t[i];
    }
    cout << travelTime(n,m,l,a,b,t) << endl;
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/

Compilation message (stderr)

/tmp/ccZmp80a.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccrb3JAd.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccrb3JAd.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status