oj.uz

Submission #962076

# Submission time Handle Problem Language Result Execution time Memory
962076 2024-04-13T06:41:46 Z Ice_man Dreaming (IOI13_dreaming) C++14
0 / 100
 44 ms 60244 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 , 0 , 1);
        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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 60244 KB Output is correct
2 Correct 43 ms 60244 KB Output is correct
3 Correct 39 ms 57076 KB Output is correct
4 Correct 16 ms 51800 KB Output is correct
5 Correct 15 ms 51108 KB Output is correct
6 Correct 19 ms 52408 KB Output is correct
7 Incorrect 11 ms 50268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 60244 KB Output is correct
2 Correct 43 ms 60244 KB Output is correct
3 Correct 39 ms 57076 KB Output is correct
4 Correct 16 ms 51800 KB Output is correct
5 Correct 15 ms 51108 KB Output is correct
6 Correct 19 ms 52408 KB Output is correct
7 Incorrect 11 ms 50268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 52828 KB Output is correct
2 Correct 26 ms 52828 KB Output is correct
3 Correct 25 ms 52692 KB Output is correct
4 Correct 25 ms 52800 KB Output is correct
5 Correct 25 ms 52828 KB Output is correct
6 Correct 28 ms 53216 KB Output is correct
7 Correct 26 ms 52828 KB Output is correct
8 Correct 25 ms 52704 KB Output is correct
9 Correct 27 ms 52696 KB Output is correct
10 Correct 26 ms 52788 KB Output is correct
11 Correct 12 ms 50264 KB Output is correct
12 Correct 13 ms 51156 KB Output is correct
13 Correct 14 ms 51020 KB Output is correct
14 Correct 13 ms 50904 KB Output is correct
15 Correct 16 ms 50952 KB Output is correct
16 Correct 14 ms 50900 KB Output is correct
17 Correct 14 ms 50904 KB Output is correct
18 Correct 14 ms 50908 KB Output is correct
19 Correct 15 ms 50900 KB Output is correct
20 Correct 11 ms 48220 KB Output is correct
21 Incorrect 12 ms 48220 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 60244 KB Output is correct
2 Correct 43 ms 60244 KB Output is correct
3 Correct 39 ms 57076 KB Output is correct
4 Correct 16 ms 51800 KB Output is correct
5 Correct 15 ms 51108 KB Output is correct
6 Correct 19 ms 52408 KB Output is correct
7 Incorrect 11 ms 50268 KB Output isn't correct
8 Halted 0 ms 0 KB -