Submission #104434

#TimeUsernameProblemLanguageResultExecution timeMemory
104434CaroLindaDreaming (IOI13_dreaming)C++14
47 / 100
176 ms11996 KiB
#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] ; 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) ; int d1 = dd[0][B1] ; int d2 = dd[2][B2] ; radio1 = findRadio(0,1 , d1) ; radio2 = findRadio(2,3 , d2) ; return max3(radio1 + radio2 + L , d1 , d2) ; }

Compilation message (stderr)

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:33:8:
     lp(i , 0 , adj[x].size() )
        ~~~~~~~~~~~~~~~~~~~~~         
dreaming.cpp:33: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:80:17: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ini(X) , dfs(X) ;
              ~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...