oj.uz

Submission #728866

# Submission time Handle Problem Language Result Execution time Memory
728866 2023-04-23T08:03:13 Z Rasoul006 Dreaming (IOI13_dreaming) C++17
0 / 100
 48 ms 15220 KB 
#include "dreaming.h"

#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

#define all(x) x.begin() , x.end()

typedef long long ll;

using namespace std;

const int N = 1e5+5;

const long long oo = 1e18 ;

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

vector <ll> vec ;

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

bool vis[N] ;

pair <ll,ll> dfs (ll u , ll p)
{
    vis[u] = true ;

    pair <ll,ll> ret = {0 , u} ;

    for (auto it : v[u])
    {
        if (it.F == p) continue ;

        pair <ll,ll> p = dfs(it.F , u) ;

        p.F += it.S ;

        ret = max(ret , p) ;
    }

    best = min(best , max(len - ret.F , ret.F) ) ;

    return ret ;
}

ll get (ll p)
{
    ll p1 , p2 ;
    p1 = dfs(p , p).S ;
    p2 = dfs(p1 , p1).S ;
    len = dfs(p1 , p1).F ;
    bans = max(bans , len);

    best = oo ;
    dfs(p1 , p1) ;

    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]});
    }

    for (int i = 0 ; i<n ; i++)
    {
        if (!vis[i])
        {
            vec.pb(get(i)) ;
            break ;
        }
    }

    while (vec.size() < 3)
        vec.pb(-oo) ;

    sort (all(vec)); reverse(all(vec));

    return max({bans , vec[0] + vec[1] + L , vec[1] + vec[2] + L + L}) ;
}

Compilation message

dreaming.cpp: In function 'll get(ll)':
dreaming.cpp:56:13: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
   56 |     ll p1 , p2 ;
      |             ^~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15220 KB Output is correct
2 Correct 48 ms 15152 KB Output is correct
3 Correct 32 ms 10896 KB Output is correct
4 Correct 8 ms 4448 KB Output is correct
5 Incorrect 5 ms 3668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15220 KB Output is correct
2 Correct 48 ms 15152 KB Output is correct
3 Correct 32 ms 10896 KB Output is correct
4 Correct 8 ms 4448 KB Output is correct
5 Incorrect 5 ms 3668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15220 KB Output is correct
2 Correct 48 ms 15152 KB Output is correct
3 Correct 32 ms 10896 KB Output is correct
4 Correct 8 ms 4448 KB Output is correct
5 Incorrect 5 ms 3668 KB Output isn't correct
6 Halted 0 ms 0 KB -