oj.uz

Submission #728457

# Submission time Handle Problem Language Result Execution time Memory
728457 2023-04-22T12:38:12 Z Rasoul006 Dreaming (IOI13_dreaming) C++17
14 / 100
 76 ms 47948 KB 
#include "dreaming.h"

#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

typedef long long ll;

using namespace std;

const int N = 1e6+5;

const long long oo = 1e18 ;

vector <pair <ll,ll>> v[N] ;

ll n , m , ans , best , mx , dis[N] , len ;

bool vis[N] ;

void dfs (ll u , ll p , ll cost)
{
    dis[u] = cost ;
    vis[u] = true ;
    for (auto it : v[u])
    {
        if (it.F != p)
            dfs(it.F , u , cost + it.S);
    }
}

bool dfs2 (ll u , ll p , ll cost , ll gol)
{
    bool is = false ;

    for (auto it : v[u])
    {
        if (it.F != p)
            is |= dfs2(it.F , u , cost + it.S , gol) ;
    }

    is |= (u == gol);

    if (is)
        best = min (best , max(cost , len-cost));

    return is ;
}

ll p1 , p2 ;

ll far (ll p)
{
    mx = 0 ; ll ret ;

    for (int i = 1 ; i<=n ; i++)
        dis[i] = 0 ;

    dfs(p , p , 0) ;

    for (int i = 1 ; i<=n ; i++)
    {
        if (dis[i] > mx)
            ret = i , mx = dis[i] ;
        dis[i] = 0 ;
    }

    return ret ;
}

ll get (ll p)
{
    p1 = far(p);
    p2 = far(p1);
    len = mx ;

    best = oo ;
    dfs2(p1 , p1 , 0 , p2) ;
    return best ;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    n = N ; m = M ;

    for (int i = 0 ; i<m ; i++)
    {
        v[B[i]].pb({A[i] , T[i]});
        v[A[i]].pb({B[i] , T[i]});
    }

    ans += get(1) ;

    ll bans = len ;

    for (int i = 1 ; i<=n ; i++)
    {
        if (!vis[i])
        {
            ans += get(i) ;
            break ;
        }
    }

    bans = max(bans , len) ;

    return max(bans , ans + L) ;
}

Compilation message

dreaming.cpp: In function 'll far(ll)':
dreaming.cpp:75:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     return ret ;
      |            ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 36972 KB Output is correct
2 Correct 59 ms 37048 KB Output is correct
3 Correct 40 ms 32468 KB Output is correct
4 Correct 18 ms 25684 KB Output is correct
5 Correct 19 ms 24944 KB Output is correct
6 Correct 23 ms 26836 KB Output is correct
7 Correct 14 ms 23796 KB Output is correct
8 Correct 33 ms 28620 KB Output is correct
9 Correct 46 ms 30468 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 61 ms 32592 KB Output is correct
12 Correct 76 ms 34996 KB Output is correct
13 Correct 13 ms 23840 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 47948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 36972 KB Output is correct
2 Correct 59 ms 37048 KB Output is correct
3 Correct 40 ms 32468 KB Output is correct
4 Correct 18 ms 25684 KB Output is correct
5 Correct 19 ms 24944 KB Output is correct
6 Correct 23 ms 26836 KB Output is correct
7 Correct 14 ms 23796 KB Output is correct
8 Correct 33 ms 28620 KB Output is correct
9 Correct 46 ms 30468 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 61 ms 32592 KB Output is correct
12 Correct 76 ms 34996 KB Output is correct
13 Correct 13 ms 23840 KB Output is correct
14 Runtime error 33 ms 47948 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 47948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 36972 KB Output is correct
2 Correct 59 ms 37048 KB Output is correct
3 Correct 40 ms 32468 KB Output is correct
4 Correct 18 ms 25684 KB Output is correct
5 Correct 19 ms 24944 KB Output is correct
6 Correct 23 ms 26836 KB Output is correct
7 Correct 14 ms 23796 KB Output is correct
8 Correct 33 ms 28620 KB Output is correct
9 Correct 46 ms 30468 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 61 ms 32592 KB Output is correct
12 Correct 76 ms 34996 KB Output is correct
13 Correct 13 ms 23840 KB Output is correct
14 Runtime error 33 ms 47948 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -