Submission #104422

#	Time	Username	Problem	Language	Result	Execution time	Memory
104422		CaroLinda	Dreaming (IOI13_dreaming)	C++14	0 / 100	59 ms	8440 KiB

dreaming

#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


using namespace std;

//declaration crap
int N , M , L;
int radio1, radio2 ;

int d[MAXN] ;
int dd[4][MAXN] ;

bool marc[MAXN] ;

vector<pii> adj[MAXN] ;

void attribution(int x)
{lp(i,0,N) dd[x][i] = d[i] ;}

void bfs(int S )
{
    memset(d , -1 , sizeof d ) ;

    queue<int> fila ;
    fila.push(S) ;
    d[S] = 0 ;

    while(!fila.empty() )
    {
        int v = fila.front() ;
        fila.pop() ;
        lp(i,0,adj[v].size())
        {
            int x = adj[v][i].ff ;
            if( d[x] != -1 ) continue ;
            d[x] = d[v] + adj[v][i].ss ;
            fila.push(x) ;
        }
    }

}

int findMax()
{
    pii p  = pii(-1,-1) ;
    lp(i,0,N)
        if( d[i] > p.ff ) p = pii(d[i] , i ) ;
    return p.ss ;
}

int findRadio(int x, int y, int diam)
{
    lp(i,0,N)
    {
        if(dd[x][i] == -1) continue ;
        int a = dd[x][i] , b = dd[y][i] ;
        a = max(a,b) ;
        diam = min(diam, a) ;
    }
    return diam ;
}

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

    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]) ) ;
    }

    bfs(0) ;
    int A1 = findMax() ;
    bfs(A1) ;
    attribution(0) ;
    int B1 = findMax() ;
    bfs(B1) ;
    attribution(1) ;

    int X ;
    lp(i,0,N)
        if(d[i] == -1) { X = i ; break ; }

    bfs(X) ;
    int A2 = findMax() ;
    bfs(A2) ;
    attribution(2) ;
    int B2 = findMax() ;
    bfs(B2) ;
    attribution(3) ;

    radio1 = findRadio(0,1 , dd[0][B1]) ;
    radio2 = findRadio(2,3 , dd[2][B2]) ;

    return radio1 + radio2 + L ;

}

Compilation message (stderr)

dreaming.cpp: In function 'void bfs(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:40:12:
         lp(i,0,adj[v].size())
            ~~~~~~~~~~~~~~~~~         
dreaming.cpp:40:9: note: in expansion of macro 'lp'
         lp(i,0,adj[v].size())
         ^~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:94:8: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]
     bfs(X) ;
     ~~~^~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23