Submission #869900

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869900	2023-11-06T07:30:05 Z	StefanL2005	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

#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[vecin] + cost[node][i]);
    }
}

void DFS_sec(int node, int p, int sum, vector<int> &best, vector<vector<int> &vec, vector<vector<int>> &cost)
{
    best[node] = sum;
    for (int i = 0; i < vec[node].size(); i++)
    {
        if (vec[node][i] == p);
            continue;

        DFS_sec(vec[node][i], node, sum + cost[node][i], best, vec, cost);
    }
}

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] = path;
    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 == main)
            path = i;
        else
            DFS_sec(vec[node][i], node, main + cost[node][i], best, vec, cost);
        if (path != -1 && temp > sec)
            sec = temp;
    }
    main -= cost[node][path];
    sec += cost[node][path];

    if (sec > main)
        DFS_sec(vec[node][path], node, sec, best, vec, cost)
    else
        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(), -1);
    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]] = B[i];
        vec[B[i]] = A[i];
        cost[A[i]] = C[i];
        cost[B[i]] = 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[node][i]] + cost[node][i];
            if (temp > unos)
            {
                dos = unos;
                unos = temp;
            }
            else
                dos = max(dos, temp);
        }
    }

    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++;
        }
    int unos = 0, dos = 0, tres = 0;

    for (int i = 0; i < hub_l.size(); i++)
        unos = max(unos, hub_l[i]);
    for (int i = 0; i < hub_l.size(); i++)
        if (hub_l[i] != unos)
            dos = max(dos, hub_l[i]);
    for (int i = 0; i < hub_l.size(); i++)
        if (hub_l[i] != unos && hub_l[i] != dos)
            tres = max(tres, hub_l[i]);

    if (M == N - 2)
        return unos + L + dos;
    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:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:15:40: error: 'vecin' was not declared in this scope; did you mean 'vec'?
   15 |         sum[node] = max(sum[node], sum[vecin] + cost[node][i]);
      |                                        ^~~~~
      |                                        vec
dreaming.cpp: At global scope:
dreaming.cpp:19:105: error: template argument 1 is invalid
   19 | void DFS_sec(int node, int p, int sum, vector<int> &best, vector<vector<int> &vec, vector<vector<int>> &cost)
      |                                                                                                         ^~~~
dreaming.cpp:19:105: error: template argument 2 is invalid
dreaming.cpp:19:105: error: template argument 1 is invalid
dreaming.cpp:19:105: error: template argument 2 is invalid
dreaming.cpp:19:105: error: template argument 1 is invalid
dreaming.cpp:19:105: error: template argument 2 is invalid
dreaming.cpp:19:59: error: 'vector' is not a type
   19 | void DFS_sec(int node, int p, int sum, vector<int> &best, vector<vector<int> &vec, vector<vector<int>> &cost)
      |                                                           ^~~~~~
dreaming.cpp:19:65: error: expected ',' or '...' before '<' token
   19 | void DFS_sec(int node, int p, int sum, vector<int> &best, vector<vector<int> &vec, vector<vector<int>> &cost)
      |                                                                 ^
dreaming.cpp: In function 'void DFS_sec(int, int, int, std::vector<int>&, int)':
dreaming.cpp:22:25: error: 'vec' was not declared in this scope
   22 |     for (int i = 0; i < vec[node].size(); i++)
      |                         ^~~
dreaming.cpp:24:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |         if (vec[node][i] == p);
      |         ^~
dreaming.cpp:25:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   25 |             continue;
      |             ^~~~~~~~
dreaming.cpp:27:43: error: 'cost' was not declared in this scope; did you mean 'cosl'?
   27 |         DFS_sec(vec[node][i], node, sum + cost[node][i], best, vec, cost);
      |                                           ^~~~
      |                                           cosl
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:33:18: error: 'path' was not declared in this scope
   33 |     best[node] = path;
      |                  ^~~~
dreaming.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:44:69: error: cannot convert 'std::vector<std::vector<int> >' to 'int'
   44 |             DFS_sec(vec[node][i], node, main + cost[node][i], best, vec, cost);
      |                                                                     ^~~
      |                                                                     |
      |                                                                     std::vector<std::vector<int> >
dreaming.cpp:19:59: note:   initializing argument 5 of 'void DFS_sec(int, int, int, std::vector<int>&, int)'
   19 | void DFS_sec(int node, int p, int sum, vector<int> &best, vector<vector<int> &vec, vector<vector<int>> &cost)
      |                                                           ^~~~~~
dreaming.cpp: In function 'int graph_hub(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
dreaming.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < best.size(); i++)
      |                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:87:21: error: 'n' was not declared in this scope
   87 |     vector<int> col(n, -1);
      |                     ^
dreaming.cpp:88:38: error: template argument 1 is invalid
   88 |     vector<vector<int> vec(n), cost(n);
      |                                      ^
dreaming.cpp:88:38: error: template argument 2 is invalid
dreaming.cpp:91:9: error: 'vec' was not declared in this scope
   91 |         vec[A[i]] = B[i];
      |         ^~~
dreaming.cpp:93:9: error: 'cost' was not declared in this scope; did you mean 'cosl'?
   93 |         cost[A[i]] = C[i];
      |         ^~~~
      |         cosl
dreaming.cpp:100:29: error: 'vec' was not declared in this scope
  100 |         DFS_sum(0, -1, sum, vec, cost, col);
      |                             ^~~
dreaming.cpp:100:34: error: 'cost' was not declared in this scope; did you mean 'cosl'?
  100 |         DFS_sum(0, -1, sum, vec, cost, col);
      |                                  ^~~~
      |                                  cosl
dreaming.cpp:104:47: error: expected ';' before ')' token
  104 |         for (int i = 0; i < vec[0].size(), i++)
      |                                               ^
      |                                               ;
dreaming.cpp:106:32: error: 'node' was not declared in this scope
  106 |             int temp = sum[vec[node][i]] + cost[node][i];
      |                                ^~~~
dreaming.cpp:119:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  119 |         if (col[i] = -1)
dreaming.cpp:121:42: error: 'vec' was not declared in this scope
  121 |             hub_l.push_back(graph_hub(i, vec, cost, col));
      |                                          ^~~
dreaming.cpp:121:47: error: 'cost' was not declared in this scope; did you mean 'cosl'?
  121 |             hub_l.push_back(graph_hub(i, vec, cost, col));
      |                                               ^~~~
      |                                               cosl
dreaming.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (int i = 0; i < hub_l.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
dreaming.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i = 0; i < hub_l.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
dreaming.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 0; i < hub_l.size(); i++)
      |                     ~~^~~~~~~~~~~~~~