Submission #104475

# Submission time Handle Problem Language Result Execution time Memory
104475 2019-04-07T00:46:47 Z CaroLinda Dreaming (IOI13_dreaming) C++14
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
//#include "dreaming.h"

#define MAXN 100005
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define max3(a,b,c) max(max(a,b),c)


using namespace std;

//declarations
int N , M , L;
int radio1, radio2 ;

int d[MAXN] , dX[MAXN];

bool marc[MAXN] ;

vector<int> radios ;
vector<pii> adj[MAXN] ;

//utilities

void atribution()
{ lp(i,0,N) dX[i] = d[i] ; }

void ini(int x)
{ memset(d , -1 , sizeof d) ; d[x] = 0 ;}

void dfs(int x)
{
    marc[x] = 1 ;
    lp(i , 0 , adj[x].size() )
    {
        int v = adj[x][i].ff ;
        if(d[v] != -1) continue ;
        d[v] = d[x] + adj[x][i].ss ;
        dfs(v) ;
    }
}

int findMax()
{ return max_element(d, d+N) - d ; }

int findRadio(int X , int Y)
{
    int ans = d[X] ;
    lp(i,0,N)
    {
        if(d[i] == -1) continue ;
        int a = d[i] , b = dX[i] ;
        a = max(a,b) ;
        ans = min(ans , a) ;
    }
    return ans ;
}


int travelTime( int n , int m , int l , int A[] , int B[] , int T[] )
{
    N = n , M = m , L = l;
    int ans = -1 ;

    vector<int> edge ;

    lp(i,0,M)
    {
        int a = A[i] , b = B[i] ;
        adj[a].pb( pii(b, T[i]) ) ;
        adj[b].pb( pii(a, T[i]) ) ;
        edge.pb(T[i]) ;
    }

    if(M < N-2)
    {
        sort(edge.begin() , edge.end()) ;
        reverse(edge.begin() , edge.end()) ;
        lp(i,0,M) ans = max(ans , edge[i]) ;
        if(M <= 3)
            lp(i,0,3) edge.pb(0) ;
        ans = max( ans , edge[0] + edge[1] + L ) ;
        ans = max( ans , edge[1] + edge[2] + 2*L ) ;
        return ans ;
    }

    lp(i,0,N)
        if(!marc[i])
        {
            ini(i) ; dfs(i) ;
            int X = findMax() ;
            ini(X) ; dfs(X) ;
            atribution() ;
            int Y = findMax() ;
            ini(Y) ; dfs(Y) ;
            int k = findRadio(X,Y) ;
            radios.pb(k) ;
            ans = max(ans, d[X]) ;
            //printf("%d %d %d\n", X, Y, k) ;
        }

    sort(radios.begin() , radios.end()) ;
    reverse(radios.begin() , radios.end() ) ;

    ans = max( ans , radios[0] + radios[1] + L ) ;

    if(radios.size() == 2) return ans ;

    ans = max( ans , radios[1] + radios[2] + 2*L ) ;

    return ans ;

}

int main()
{
    int n , m , l , a[MAXN] , b[MAXN] , t[MAXN] ;
    scanf("%d %d %d", &n, &m, &l) ;
    lp(i,0,m) scanf("%d%d%d", &a[i] , &b[i] , &t[i]) ;
    printf("%d\n",travelTime(n,m,l,a,b,t)) ;
}

Compilation message

dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:5:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i = a ; i < b ; i++)
dreaming.cpp:37:8:
     lp(i , 0 , adj[x].size() )
        ~~~~~~~~~~~~~~~~~~~~~         
dreaming.cpp:37:5: note: in expansion of macro 'lp'
     lp(i , 0 , adj[x].size() )
     ^~
dreaming.cpp: In function 'int main()':
dreaming.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &l) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:122:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     lp(i,0,m) scanf("%d%d%d", &a[i] , &b[i] , &t[i]) ;
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/cc7aLSQt.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccLTIRGl.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccLTIRGl.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status