oj.uz

Submission #728447

# Submission time Handle Problem Language Result Execution time Memory
728447 2023-04-22T12:14:26 Z Rasoul006 Dreaming (IOI13_dreaming) C++17
0 / 100
 54 ms 36988 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] , dis2[N] ;

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 , mx-cost)) ;

    return is ;
}

ll p1 , p2 ;

ll get (ll p)
{
    mx = 0 ;
    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)
            p1 = i , mx = dis[i] ;
        dis[i] = 0 ;
    }

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

    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 ;

    ll sum = 0 ;

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

    ans += get(1) ;

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

    return ans + L ;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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