oj.uz

Submission #291977

# Submission time Handle Problem Language Result Execution time Memory
291977 2020-09-06T06:34:30 Z Badrangiikh Dreaming (IOI13_dreaming) C++14
32 / 100
 91 ms 32888 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;

int ans , maxx , x , y ;
int pare [ 1000005 ] ;
int a [ 1000005 ] ;
pair < int , int > pr , prr , pp ;
vector < pair < int , int > > vc [ 1000005 ] ;
vector < int > vec ;
bool used [ 1000005 ] ;


pair < int , int > dfs ( int chi , int par ) {
    used [ chi ] = 1 ;
    prr = { 0 , chi } ;
    for( auto &u : vc [ chi ] ) {
        if ( u . second == par ) continue;
        pp = dfs ( u . second , chi ) ;
        prr = max ( prr , { pp . first + u . first , pp . second } ) ;
    }
    a [ chi ] = prr . first ;
    pare [ chi ] = par ;
    return prr ; 
}
int travelTime (int N, int M, int L, int A[], int B[], int T[]) {
    for ( int i = 0 ; i < M ; i ++ ) {
        vc [ A [ i ] ] . push_back ( { T [ i ] , B [ i ] } ) ;
        vc [ B [ i ] ] . push_back ( { T [ i ] , A [ i ] } ) ;
    }
    for ( int i = 0 ; i < N ; i ++ ) {
        if ( used [ i ] != 0 ) continue ;
        pr = dfs ( dfs ( i , -1 ) . second , -1 ) ;
        x = pr . second ;
        y = pr . first ;
        for ( int j = x ; j >= 0 ; j = pare [ j ] ) {
            y = min ( y , max ( a [ j ] , pr . first - a [ j ] ) ) ;
        }
        vec . push_back ( y ) ; 
        maxx = max ( maxx , pr. first ) ; 
    }
    sort ( vec . rbegin ( ) , vec . rend ( ) ) ;
    if ( vec . size ( ) > 2 ) {
        ans = L + vec [ 0 ] + vec [ 1 ] ;
        for ( int i = 2 ; i < vec . size ( ) ; i ++ ) {
            ans = max ( ans , L + L + vec [ 1 ] + vec [ i ] ) ;
        }
    }
    else {
        if ( vec . size ( ) == 2 ) ans = L + vec [ 0 ] + vec [ 1 ] ;
        else ans = 0 ;
    }
    ans = max ( ans , maxx ) ;
    return ans ;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:45:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for ( int i = 2 ; i < vec . size ( ) ; i ++ ) {
      |                           ~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32888 KB Output is correct
2 Correct 77 ms 32760 KB Output is correct
3 Correct 62 ms 29688 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 28 ms 24568 KB Output is correct
6 Correct 28 ms 25856 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 44 ms 27008 KB Output is correct
9 Correct 49 ms 28280 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 81 ms 29720 KB Output is correct
12 Correct 91 ms 31224 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32888 KB Output is correct
2 Correct 77 ms 32760 KB Output is correct
3 Correct 62 ms 29688 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 28 ms 24568 KB Output is correct
6 Correct 28 ms 25856 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 44 ms 27008 KB Output is correct
9 Correct 49 ms 28280 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 81 ms 29720 KB Output is correct
12 Correct 91 ms 31224 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Incorrect 17 ms 23808 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32888 KB Output is correct
2 Correct 77 ms 32760 KB Output is correct
3 Correct 62 ms 29688 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 28 ms 24568 KB Output is correct
6 Correct 28 ms 25856 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 44 ms 27008 KB Output is correct
9 Correct 49 ms 28280 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 81 ms 29720 KB Output is correct
12 Correct 91 ms 31224 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Incorrect 17 ms 23808 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 27384 KB Output is correct
2 Correct 47 ms 27420 KB Output is correct
3 Correct 44 ms 27384 KB Output is correct
4 Correct 50 ms 27384 KB Output is correct
5 Correct 46 ms 27384 KB Output is correct
6 Correct 45 ms 27768 KB Output is correct
7 Correct 45 ms 27512 KB Output is correct
8 Correct 43 ms 27256 KB Output is correct
9 Correct 43 ms 27288 KB Output is correct
10 Correct 46 ms 27520 KB Output is correct
11 Correct 17 ms 23808 KB Output is correct
12 Correct 22 ms 25340 KB Output is correct
13 Correct 23 ms 25340 KB Output is correct
14 Correct 23 ms 25340 KB Output is correct
15 Correct 23 ms 25340 KB Output is correct
16 Correct 23 ms 25340 KB Output is correct
17 Correct 22 ms 25212 KB Output is correct
18 Correct 23 ms 25460 KB Output is correct
19 Correct 23 ms 25340 KB Output is correct
20 Correct 16 ms 23808 KB Output is correct
21 Correct 16 ms 23808 KB Output is correct
22 Correct 17 ms 23936 KB Output is correct
23 Correct 22 ms 25340 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32888 KB Output is correct
2 Correct 77 ms 32760 KB Output is correct
3 Correct 62 ms 29688 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 28 ms 24568 KB Output is correct
6 Correct 28 ms 25856 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 44 ms 27008 KB Output is correct
9 Correct 49 ms 28280 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 81 ms 29720 KB Output is correct
12 Correct 91 ms 31224 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Incorrect 17 ms 23936 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32888 KB Output is correct
2 Correct 77 ms 32760 KB Output is correct
3 Correct 62 ms 29688 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 28 ms 24568 KB Output is correct
6 Correct 28 ms 25856 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 44 ms 27008 KB Output is correct
9 Correct 49 ms 28280 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 81 ms 29720 KB Output is correct
12 Correct 91 ms 31224 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Incorrect 17 ms 23808 KB Output isn't correct
15 Halted 0 ms 0 KB -