oj.uz

Submission #728857

# Submission time Handle Problem Language Result Execution time Memory
728857 2023-04-23T07:51:42 Z Rasoul006 Dreaming (IOI13_dreaming) C++17
14 / 100
 87 ms 37056 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 = 0 ; i<n ; i++)
        dis[i] = 0 ;
 
    dfs(p , p , 0) ;
 
    for (int i = 0 ; i<n ; i++)
    {
        if (dis[i] >= mx)
            p1 = i , mx = dis[i] ;
        dis[i] = 0 ;
    }
 
    mx = 0 ;
    dfs(p1 , p1 , 0) ;
    for (int i = 0 ; 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++)
    {
        v[B[i]].pb({A[i] , T[i]});
        v[A[i]].pb({B[i] , T[i]});
    }
 
    ans += get(0) ;
 
    ll bans = mx ;
 
    for (int i = 0 ; i<n ; i++)
    {
        if (!vis[i])
        {
            ans += get(i) ;
            break ;
        }
    }
 
    bans = max(bans , mx) ;
 
    return max(bans , ans + L) ;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:91:8: warning: unused variable 'sum' [-Wunused-variable]
   91 |     ll sum = 0 ;
      |        ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 37056 KB Output is correct
2 Correct 87 ms 36960 KB Output is correct
3 Correct 41 ms 32392 KB Output is correct
4 Correct 21 ms 25684 KB Output is correct
5 Correct 17 ms 24916 KB Output is correct
6 Correct 28 ms 26852 KB Output is correct
7 Correct 18 ms 23860 KB Output is correct
8 Correct 49 ms 28580 KB Output is correct
9 Correct 44 ms 30540 KB Output is correct
10 Correct 15 ms 23820 KB Output is correct
11 Correct 74 ms 32484 KB Output is correct
12 Correct 77 ms 34900 KB Output is correct
13 Correct 13 ms 23892 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 37056 KB Output is correct
2 Correct 87 ms 36960 KB Output is correct
3 Correct 41 ms 32392 KB Output is correct
4 Correct 21 ms 25684 KB Output is correct
5 Correct 17 ms 24916 KB Output is correct
6 Correct 28 ms 26852 KB Output is correct
7 Correct 18 ms 23860 KB Output is correct
8 Correct 49 ms 28580 KB Output is correct
9 Correct 44 ms 30540 KB Output is correct
10 Correct 15 ms 23820 KB Output is correct
11 Correct 74 ms 32484 KB Output is correct
12 Correct 77 ms 34900 KB Output is correct
13 Correct 13 ms 23892 KB Output is correct
14 Incorrect 16 ms 23720 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 37056 KB Output is correct
2 Correct 87 ms 36960 KB Output is correct
3 Correct 41 ms 32392 KB Output is correct
4 Correct 21 ms 25684 KB Output is correct
5 Correct 17 ms 24916 KB Output is correct
6 Correct 28 ms 26852 KB Output is correct
7 Correct 18 ms 23860 KB Output is correct
8 Correct 49 ms 28580 KB Output is correct
9 Correct 44 ms 30540 KB Output is correct
10 Correct 15 ms 23820 KB Output is correct
11 Correct 74 ms 32484 KB Output is correct
12 Correct 77 ms 34900 KB Output is correct
13 Correct 13 ms 23892 KB Output is correct
14 Incorrect 16 ms 23720 KB Output isn't correct
15 Halted 0 ms 0 KB -