oj.uz

Submission #104474

# Submission time Handle Problem Language Result Execution time Memory
104474 2019-04-07T00:39:16 Z CaroLinda Dreaming (IOI13_dreaming) C++14
14 / 100
 1000 ms 10332 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];
int degree[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[Y] ;
    lp(i,0,N)
    {
        if(d[i] == -1) continue ;
        int a = d[i] , b = d[Y] - a ;
        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 ;

    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]) ) ;
        degree[a]++ ;
        degree[b]++ ;
    }

    lp(i,0,N)
        if(!marc[i] and degree[i] == 1)
        {
            ini(i) ; dfs(i) ;
            int X = findMax() ;
            ini(X) ; dfs(X) ;
            int Y = findMax() ;
            int k = findRadio(X,Y) ;
            radios.pb(k) ;
            ans = max(ans , d[Y]) ;
            //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:38:8:
     lp(i , 0 , adj[x].size() )
        ~~~~~~~~~~~~~~~~~~~~~         
dreaming.cpp:38:5: note: in expansion of macro 'lp'
     lp(i , 0 , adj[x].size() )
     ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10232 KB Output is correct
2 Correct 59 ms 10332 KB Output is correct
3 Correct 38 ms 7800 KB Output is correct
4 Correct 12 ms 4096 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 17 ms 4608 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 29 ms 5760 KB Output is correct
9 Correct 38 ms 6776 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct
11 Correct 49 ms 7928 KB Output is correct
12 Correct 71 ms 9080 KB Output is correct
13 Correct 5 ms 3200 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10232 KB Output is correct
2 Correct 59 ms 10332 KB Output is correct
3 Correct 38 ms 7800 KB Output is correct
4 Correct 12 ms 4096 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 17 ms 4608 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 29 ms 5760 KB Output is correct
9 Correct 38 ms 6776 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct
11 Correct 49 ms 7928 KB Output is correct
12 Correct 71 ms 9080 KB Output is correct
13 Correct 5 ms 3200 KB Output is correct
14 Correct 4 ms 3072 KB Output is correct
15 Correct 5 ms 3072 KB Output is correct
16 Incorrect 4 ms 3072 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10232 KB Output is correct
2 Correct 59 ms 10332 KB Output is correct
3 Correct 38 ms 7800 KB Output is correct
4 Correct 12 ms 4096 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 17 ms 4608 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 29 ms 5760 KB Output is correct
9 Correct 38 ms 6776 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct
11 Correct 49 ms 7928 KB Output is correct
12 Correct 71 ms 9080 KB Output is correct
13 Correct 5 ms 3200 KB Output is correct
14 Correct 4 ms 3072 KB Output is correct
15 Correct 5 ms 3072 KB Output is correct
16 Incorrect 4 ms 3072 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 6016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10232 KB Output is correct
2 Correct 59 ms 10332 KB Output is correct
3 Correct 38 ms 7800 KB Output is correct
4 Correct 12 ms 4096 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 17 ms 4608 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 29 ms 5760 KB Output is correct
9 Correct 38 ms 6776 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct
11 Correct 49 ms 7928 KB Output is correct
12 Correct 71 ms 9080 KB Output is correct
13 Correct 5 ms 3200 KB Output is correct
14 Correct 12 ms 3072 KB Output is correct
15 Correct 20 ms 3380 KB Output is correct
16 Correct 31 ms 3200 KB Output is correct
17 Correct 11 ms 3200 KB Output is correct
18 Correct 18 ms 3200 KB Output is correct
19 Correct 26 ms 3200 KB Output is correct
20 Correct 9 ms 3200 KB Output is correct
21 Correct 16 ms 3200 KB Output is correct
22 Correct 23 ms 3200 KB Output is correct
23 Correct 4 ms 3072 KB Output is correct
24 Correct 4 ms 3072 KB Output is correct
25 Correct 4 ms 3072 KB Output is correct
26 Incorrect 4 ms 3072 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10232 KB Output is correct
2 Correct 59 ms 10332 KB Output is correct
3 Correct 38 ms 7800 KB Output is correct
4 Correct 12 ms 4096 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 17 ms 4608 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 29 ms 5760 KB Output is correct
9 Correct 38 ms 6776 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct
11 Correct 49 ms 7928 KB Output is correct
12 Correct 71 ms 9080 KB Output is correct
13 Correct 5 ms 3200 KB Output is correct
14 Correct 4 ms 3072 KB Output is correct
15 Correct 5 ms 3072 KB Output is correct
16 Incorrect 4 ms 3072 KB Output isn't correct
17 Halted 0 ms 0 KB -