oj.uz

Submission #870079

# Submission time Handle Problem Language Result Execution time Memory
870079 2023-11-06T21:56:27 Z StefanL2005 Dreaming (IOI13_dreaming) C++14
0 / 100
 1000 ms 17280 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

int k = 0;
 
void DFS_sum(int node, int p, vector<int> &sum, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &col)
{
    col[node] = k;
    for (int i = 0; i < vec[node].size(); i++)
    {
        if (vec[node][i] == p)
            continue;
 
        DFS_sum(vec[node][i], node, sum, vec, cost, col);
        sum[node] = max(sum[node], sum[vec[node][i]] + cost[node][i]);
    }
}

void DFS_main(int node, int p, int main, int sec, vector<int> &sum, vector<int> &best, vector<vector<int>> &vec, vector<vector<int>> &cost)
{
    best[node] = main;
    int path = -1;
    for (int i = 0; i < vec[node].size(); i++)
    {
        int temp = sum[vec[node][i]] + cost[node][i];
        if (vec[node][i] == p)
            continue;

        if (temp > sec && (temp != main || path != -1))
            sec = temp;
        
        if (temp == main)
            path = i;
    }

    if (path == -1)
        return;
    main = sum[vec[node][path]];
    sec += cost[node][path];
 
    if (sec > main)
    {
        best[vec[node][path]] = sec;
        return;
    }
    DFS_main(vec[node][path], node, main, sec, sum, best, vec, cost);
}
 
int graph_hub(int node, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &col)
{
    vector<int> sum(vec.size(), 0);
    DFS_sum(node, -1, sum, vec, cost, col);
    
    int MAX = 0, sec = 0;
    for (int i = 0; i < vec[node].size(); i++)
    {
        int temp = sum[vec[node][i]] + cost[node][i];
 
        if (temp > MAX)
        {
            sec = MAX;
            MAX = temp;
        }
        else
            sec = max(sec, temp);
    }

    vector<int> best(vec.size(), 1000 * 1000 * 1000);
    DFS_main(node, -1, MAX, sec, sum, best, vec, cost);

    int Min = best[0];
    for (int i = 0; i < best.size(); i++)
        Min = min(best[i], Min);
    
    return Min;
}
int travelTime(int N, int M, int L, int A[], int B[], int C[])
{
    vector<int> col(N, -1);
    vector<vector<int>> vec(N), cost(N);
    for (int i = 0; i < M; i++)
    {
        vec[A[i]].push_back(B[i]);
        vec[B[i]].push_back(A[i]);
        cost[A[i]].push_back(C[i]);
        cost[B[i]].push_back(C[i]);
    }

    if (M == N - 1)
    {
        vector<int> sum(N, 0);
        DFS_sum(0, -1, sum, vec, cost, col);
 
        int unos = 0, dos = 0;
 
        for (int i = 0; i < vec[0].size(); i++)
       {
            int temp = sum[vec[0][i]] + cost[0][i];
            if (temp > unos)
            {
                dos = unos;
                unos = temp;
             }
            else
                dos = max(dos, temp);
        }
        return unos + dos;
    }

    vector<int> hub_l;
    for (int i = 0; i < N; i++)
        if (col[i] == -1)
        {
            hub_l.push_back(graph_hub(i, vec, cost, col));
            k++;
        }
    
    sort(hub_l.begin(), hub_l.end());
    int unos, dos, tres;
    unos = hub_l[hub_l.size() - 1];
    dos = hub_l[hub_l.size() - 2];
    
    if (M == N - 2)
        return unos + L + dos;
    
    tres = hub_l[hub_l.size() - 3];
    return max(unos + L + dos, dos + 2 * L + tres);
}

Compilation message

dreaming.cpp: In function 'void DFS_sum(int, int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
dreaming.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void DFS_main(int, int, int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
dreaming.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int graph_hub(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
dreaming.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < best.size(); i++)
      |                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int i = 0; i < vec[0].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 10492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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