Submission #104479

#	Time	Username	Problem	Language	Result	Execution time	Memory
104479		CaroLinda	Dreaming (IOI13_dreaming)	C++14	100 / 100	160 ms	14672 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
#define max3(a,b,c) max(max(a,b),c)
 
 
using namespace std;
 
//declarations
int N , M , L;
 
int d[MAXN] , p[MAXN];
 
bool marc[MAXN] ;
 
vector<int> radios , vv;
vector<pii> adj[MAXN] ;
 
//utilities
 
void ini(int x)
{ vv.resize(0) ; p[x] = -1 ; d[x] = 0 ;}
 
void dfs(int x)
{
    marc[x] = 1 ;
    lp(i , 0 , adj[x].size() )
    {
        int v = adj[x][i].ff ;
        if( p[x] == v ) continue ;
        d[v] = d[x] + adj[x][i].ss ;
        p[v] = x ;
        vv.pb(v) ;
        dfs(v) ;
    }
}
 
int findMax(int x)
{
  lp(i,0,vv.size())
  {
    int v = vv[i] ;
    if(d[v] > d[x]) x = v ;
  }
  return x ;
}
 
int findRadio(int diam , int x)
{
    int ans = diam ;
    for(int i = x ; i != -1 ; i = p[i])
          ans = min( ans , max(d[i] , diam - d[i]) ) ;
    return ans ;
}
 
 
int travelTime( int n , int m , int l , int A[] , int B[] , int T[] )
{
    N = n , M = m , L = l;
    int ans = 0 ;
 
    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]) ) ;
    }
 
    lp(i,0,N)
        if(!marc[i])
        {
            ini(i) ; dfs(i) ;
            int X = findMax(i) ;
            ini(X) ; dfs(X) ;
            int Y = findMax(X) ;
            int diameter = d[Y] ;
            int k = diameter ;
            for(int j = Y ; j!=-1 ; j = p[j])
              k = min( k , max( d[j] , diameter-d[j] ) ) ;
            radios.pb(k) ;
            ans = max(ans , diameter) ;
        }
 
    sort(radios.begin() , radios.end()) ;
    reverse(radios.begin() , radios.end() ) ;
 
    if(radios.size()>=2) 
      ans = max( ans , radios[0] + radios[1] + L ) ;
 
    if(radios.size() == 2) return ans ;
 
    if(radios.size()>=3)
     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 (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 findMax(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:46:6:
   lp(i,0,vv.size())
      ~~~~~~~~~~~~~                   
dreaming.cpp:46:3: note: in expansion of macro 'lp'
   lp(i,0,vv.size())
   ^~

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