oj.uz

Submission #962078

# Submission time Handle Problem Language Result Execution time Memory
962078 2024-04-13T06:42:49 Z Ice_man Dreaming (IOI13_dreaming) C++14
32 / 100
 52 ms 60640 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include"dreaming.h".
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>

#define maxn 2000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}*/

typedef pair <int , int> pii;


vector <pii> v[maxn];
bool used[maxn];


pii dfs(int node , int _par , int depth)
{
    int current = 0 , cur_ans = depth;
    pii _try;

    for(pii nb : v[node])
    {
        if(nb.X == _par)
            continue;

        _try = dfs(nb.X , node , depth + nb.Y);
        if(_try.X + nb.Y > current)
        {
            current = _try.X + nb.Y;
            cur_ans = min(_try.Y , max(depth , current));
        }
    }
    return make_pair(current , cur_ans);
}



pii f(int node , int _par)
{
    used[node] = true;
    pii current;
    current.X = 0;
    current.Y = node;
    pii current2;

    for(pii nb : v[node])
    {
        if(nb.X == _par)
            continue;

        current2 = f(nb.X , node);
        current2.X += nb.Y;
        current = max(current , current2);
    }

    return current;
}




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

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

    vector <int> distances;

    for(int i = 0; i < N; i++)
    {
        if(used[i] == true)
            continue;

        int dist = f(i , 1).Y;
        pii cur_ans = dfs(dist , 1 , 0);
        ans = max(ans , cur_ans.X);
        distances.pb(cur_ans.Y);
    }


    sort(distances.begin() , distances.end());
    reverse(distances.begin() , distances.end());

    if(distances.size() > 1)
        ans = max(ans , distances[0] + distances[1] + L);
    if(distances.size() > 2)
        ans = max(ans , distances[1] + distances[2] + (2 * L));
    return ans;
}






/**int main()
{

    #ifdef ONLINE_JUDGE /// promeni
        freopen("taxi.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //startT = std::chrono::high_resolution_clock::now();


    read();
    solve();

    return 0;
}*/

Compilation message

dreaming.cpp:9:21: warning: extra tokens at end of #include directive
    9 | #include"dreaming.h".
      |                     ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 60640 KB Output is correct
2 Correct 49 ms 60236 KB Output is correct
3 Correct 33 ms 56920 KB Output is correct
4 Correct 17 ms 51804 KB Output is correct
5 Correct 15 ms 51036 KB Output is correct
6 Correct 20 ms 52620 KB Output is correct
7 Correct 11 ms 50264 KB Output is correct
8 Correct 28 ms 53444 KB Output is correct
9 Correct 32 ms 54996 KB Output is correct
10 Correct 11 ms 50268 KB Output is correct
11 Correct 42 ms 56424 KB Output is correct
12 Correct 47 ms 58192 KB Output is correct
13 Correct 11 ms 50268 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 50364 KB Output is correct
2 Correct 12 ms 50264 KB Output is correct
3 Correct 12 ms 50268 KB Output is correct
4 Correct 12 ms 50264 KB Output is correct
5 Correct 11 ms 50180 KB Output is correct
6 Incorrect 12 ms 50368 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 60640 KB Output is correct
2 Correct 49 ms 60236 KB Output is correct
3 Correct 33 ms 56920 KB Output is correct
4 Correct 17 ms 51804 KB Output is correct
5 Correct 15 ms 51036 KB Output is correct
6 Correct 20 ms 52620 KB Output is correct
7 Correct 11 ms 50264 KB Output is correct
8 Correct 28 ms 53444 KB Output is correct
9 Correct 32 ms 54996 KB Output is correct
10 Correct 11 ms 50268 KB Output is correct
11 Correct 42 ms 56424 KB Output is correct
12 Correct 47 ms 58192 KB Output is correct
13 Correct 11 ms 50268 KB Output is correct
14 Correct 12 ms 50364 KB Output is correct
15 Correct 12 ms 50264 KB Output is correct
16 Correct 12 ms 50268 KB Output is correct
17 Correct 12 ms 50264 KB Output is correct
18 Correct 11 ms 50180 KB Output is correct
19 Incorrect 12 ms 50368 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 52824 KB Output is correct
2 Correct 26 ms 52828 KB Output is correct
3 Correct 31 ms 52692 KB Output is correct
4 Correct 25 ms 52828 KB Output is correct
5 Correct 26 ms 52748 KB Output is correct
6 Correct 30 ms 53216 KB Output is correct
7 Correct 27 ms 52828 KB Output is correct
8 Correct 26 ms 52700 KB Output is correct
9 Correct 27 ms 52692 KB Output is correct
10 Correct 27 ms 52828 KB Output is correct
11 Correct 12 ms 50268 KB Output is correct
12 Correct 14 ms 50904 KB Output is correct
13 Correct 14 ms 50800 KB Output is correct
14 Correct 14 ms 50904 KB Output is correct
15 Correct 14 ms 50904 KB Output is correct
16 Correct 14 ms 51020 KB Output is correct
17 Correct 13 ms 50792 KB Output is correct
18 Correct 14 ms 51456 KB Output is correct
19 Correct 14 ms 50904 KB Output is correct
20 Correct 11 ms 48084 KB Output is correct
21 Correct 13 ms 48216 KB Output is correct
22 Correct 13 ms 50268 KB Output is correct
23 Correct 14 ms 50904 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 50364 KB Output is correct
2 Correct 12 ms 50264 KB Output is correct
3 Correct 12 ms 50268 KB Output is correct
4 Correct 12 ms 50264 KB Output is correct
5 Correct 11 ms 50180 KB Output is correct
6 Incorrect 12 ms 50368 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 60640 KB Output is correct
2 Correct 49 ms 60236 KB Output is correct
3 Correct 33 ms 56920 KB Output is correct
4 Correct 17 ms 51804 KB Output is correct
5 Correct 15 ms 51036 KB Output is correct
6 Correct 20 ms 52620 KB Output is correct
7 Correct 11 ms 50264 KB Output is correct
8 Correct 28 ms 53444 KB Output is correct
9 Correct 32 ms 54996 KB Output is correct
10 Correct 11 ms 50268 KB Output is correct
11 Correct 42 ms 56424 KB Output is correct
12 Correct 47 ms 58192 KB Output is correct
13 Correct 11 ms 50268 KB Output is correct
14 Correct 12 ms 50364 KB Output is correct
15 Correct 12 ms 50264 KB Output is correct
16 Correct 12 ms 50268 KB Output is correct
17 Correct 12 ms 50264 KB Output is correct
18 Correct 11 ms 50180 KB Output is correct
19 Incorrect 12 ms 50368 KB Output isn't correct
20 Halted 0 ms 0 KB -