oj.uz

Submission #104431

# Submission time Handle Problem Language Result Execution time Memory
104431 2019-04-06T19:28:29 Z CaroLinda Dreaming (IOI13_dreaming) C++14
0 / 100
 77 ms 11384 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


using namespace std;

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

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

vector<pii> adj[MAXN] ;

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

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

void dfs(int x)
{
    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 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]) ) ;
    }

    ini(0) ; dfs(0) ;
    int A1 = findMax() ;
    ini(A1) , dfs(A1) ;
    atribution(0) ;
    int B1 = findMax() ;
    ini(B1) , dfs(B1) ;
    atribution(1) ;

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

    ini(X) , dfs(X) ;
    int A2 = findMax() ;
    ini(A2) , dfs(A2) ;
    atribution(2) ;
    int B2 = findMax() ;
    ini(B2) , dfs(B2) ;
    atribution(3) ;

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

    return radio1 + radio2 + L ;

}

/*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:32:8:
     lp(i , 0 , adj[x].size() )
        ~~~~~~~~~~~~~~~~~~~~~         
dreaming.cpp:32:5: note: in expansion of macro 'lp'
     lp(i , 0 , adj[x].size() )
     ^~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:79:17: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ini(X) , dfs(X) ;
              ~~~^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -