Submission #1280995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280995		monval	Dreaming (IOI13_dreaming)	C++20	Compilation error	0 ms	0 KiB

dreaming

#include "dreaming.h"

#include <vector>
#include <tuple>
#include <unordered_set>
#include <forward_list>

void swap(int &a, int &b){
    int t = a;
    a = b;
    b = t;
}

int min(int a, int b){
    if(a < b){
        return a;
    }else{
        return b;
    }
}

int max(int a, int b){
    if(a < b){
        return b;
    }else{
        return a;
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    int root_vertices[N - M];
    unordered_set<int> child_edges[N];
    int components[N];
    for(int i = 0; i < N; i++){
        components[i] = -1;
    }
    for(int i = 0; i < M; i++){
        child_edges[A[i]].insert(i);
        child_edges[B[i]].insert(i);
    }
    int eccentricities[N];
    int current_component = 0;
    int current_root = 0;
    while(current_component < N - M){
        if(components[current_root] != -1 || child_edges[current_root].size() > 1){
            current_root++;
            continue;
        }
        if(child_edges[current_root].empty()){
            components[current_root] = current_component;
            eccentricities[current_root] = 0;
            current_root++;
            current_component++;
            continue;
        }
        root_vertices[current_component] = current_root;
        forward_list<int> children = {current_root};
        while(!children.empty()){
            int child = children.front();
            children.pop_front();
            components[child] = current_component;
            for(int edge : child_edges[child]){
                if(A[edge] != child){
                    swap(A[edge], B[edge]);
                }
                child_edges[B[edge]].erase(edge);
                children.push_front(B[edge]);
            }
        }
        current_root++;
        current_component++;
    }
    int heights[N];
    int height_edges[N];
    for(int i = 0; i < N; i++){
        heights[i] = 0;
        height_edges[i] = -1;
    }
    forward_list<tuple<int, bool> > height_calculation;
    for(int i = 0; i < N - M; i++){
        height_calculation.push_front(make_tuple(root_vertices[i], false));
    }
    while(!height_calculation.empty()){
        int vertex;
        bool status;
        tie(vertex, status) = height_calculation.front();
        height_calculation.pop_front();
        if(status){
            for(int edge : child_edges[vertex]){
                int new_height = heights[B[edge]] + T[edge];
                if(new_height > heights[vertex]){
                    heights[vertex] = new_height;
                    height_edges[vertex] = edge;
                }
            }
        }else{
            height_calculation.push_front(make_tuple(vertex, true));
            for(int edge : child_edges[vertex]){
                height_calculation.push_front(make_tuple(B[edge], false));
            }
        }
    }
    vector<int> max_paths[N - M];
    for(int component = 0; component < N - M; component++){
        int root = root_vertices[component];
        max_paths[component] = {root};
        while(true){
            int last_vertex = max_paths[component].back();
            if(height_edges[last_vertex] == -1){
                break;
            }
            child_edges[last_vertex].erase(height_edges[last_vertex]);
            max_paths[component].push_back(B[height_edges[last_vertex]]);
        }
    }
    for(int component = 0; component < N - M; component++){
        int best_upward[max_paths[component].size()];
        best_upward[0] = 0;
        for(int i = 1; i < max_paths[component].size(); i++){
            best_upward[i] = best_upward[i - 1] + T[height_edges[max_paths[component][i - 1]]];
            for(int edge : child_edges[max_paths[component][i]]){
                int new_best = heights[B[edge]] + T[edge];
                best_upward[i] = max(best_upward[i], new_best);
            }
        }
        for(int i = 0; i < max_paths[component].size(); i++){
            eccentricities[max_paths[component][i]] = max(heights[max_paths[component][i]], best_upward[i]);
        }
    }
    forward_list<int> eccentricity_calculation;
    for(vector<int> max_path : max_paths){
        for(int vertex : max_path){
            eccentricity_calculation.push_front(vertex);
        }
    }
    while(!eccentricity_calculation.empty()){
        int vertex = eccentricity_calculation.front();
        eccentricity_calculation.pop_front();
        for(int edge : child_edges[vertex]){
            eccentricities[B[edge]] = eccentricities[vertex] + T[edge];
            eccentricity_calculation.push_front(B[edge]);
        }
    }
    int diameters[N - M];
    int radii[N - M];
    for(int i = 0; i < N - M; i++){
        diameters[i] = 0;
        radii[i] = eccentricities[root_vertices[i]];
    }
    for(int vertex = 0; vertex < N; vertex++){
        diameters[components[vertex]] = max(diameters[components[vertex]], eccentricities[vertex]);
        radii[components[vertex]] = min(radii[components[vertex]], eccentricities[vertex]);
    }
    int min_diameter = 0;
    for(int i = 0; i < N - M; i++){
        min_diameter = max(min_diameter, diameters[i]);
    }
    if(N - M == 1){
        ;
    }else if(N - M == 2){
        min_diameter = max(min_diameter, radii[0] + radii[1] + L);
    }else{
        int r1 = 0, r2 = 0, r3 = 0;
        for(int i = 0; i < N - M; i++){
            if(radii[i] >= r1){
                r3 = r2;
                r2 = r1;
                r1 = radii[i];
            }else if(radii[i] >= r2){
                r3 = r2;
                r2 = radii[i];
            }else if(radii[i] >= r3){
                r3 = radii[i];
            }
        }
        min_diameter = max(min_diameter, r1 + r2 + L);
        min_diameter = max(min_diameter, r2 + r3 + 2 * L);
    }
    return min_diameter;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:32:5: error: 'unordered_set' was not declared in this scope
   32 |     unordered_set<int> child_edges[N];
      |     ^~~~~~~~~~~~~
dreaming.cpp:32:5: note: suggested alternatives:
In file included from /usr/include/c++/13/unordered_set:41,
                 from dreaming.cpp:5:
/usr/include/c++/13/bits/unordered_set.h:104:11: note:   'std::unordered_set'
  104 |     class unordered_set
      |           ^~~~~~~~~~~~~
/usr/include/c++/13/unordered_set:58:13: note:   'std::pmr::unordered_set'
   58 |       using unordered_set
      |             ^~~~~~~~~~~~~
dreaming.cpp:32:19: error: expected primary-expression before 'int'
   32 |     unordered_set<int> child_edges[N];
      |                   ^~~
dreaming.cpp:38:9: error: 'child_edges' was not declared in this scope
   38 |         child_edges[A[i]].insert(i);
      |         ^~~~~~~~~~~
dreaming.cpp:45:46: error: 'child_edges' was not declared in this scope
   45 |         if(components[current_root] != -1 || child_edges[current_root].size() > 1){
      |                                              ^~~~~~~~~~~
dreaming.cpp:49:12: error: 'child_edges' was not declared in this scope
   49 |         if(child_edges[current_root].empty()){
      |            ^~~~~~~~~~~
dreaming.cpp:57:9: error: 'forward_list' was not declared in this scope
   57 |         forward_list<int> children = {current_root};
      |         ^~~~~~~~~~~~
dreaming.cpp:57:9: note: suggested alternatives:
In file included from /usr/include/c++/13/forward_list:40,
                 from dreaming.cpp:6:
/usr/include/c++/13/bits/forward_list.h:433:11: note:   'std::forward_list'
  433 |     class forward_list : private _Fwd_list_base<_Tp, _Alloc>
      |           ^~~~~~~~~~~~
/usr/include/c++/13/forward_list:56:13: note:   'std::pmr::forward_list'
   56 |       using forward_list = std::forward_list<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~~~~~~~
dreaming.cpp:57:22: error: expected primary-expression before 'int'
   57 |         forward_list<int> children = {current_root};
      |                      ^~~
dreaming.cpp:58:16: error: 'children' was not declared in this scope
   58 |         while(!children.empty()){
      |                ^~~~~~~~
dreaming.cpp:62:28: error: 'child_edges' was not declared in this scope
   62 |             for(int edge : child_edges[child]){
      |                            ^~~~~~~~~~~
dreaming.cpp:79:18: error: 'tuple' was not declared in this scope; did you mean 'std::tuple'?
   79 |     forward_list<tuple<int, bool> > height_calculation;
      |                  ^~~~~
      |                  std::tuple
In file included from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/vector:62,
                 from dreaming.cpp:3:
/usr/include/c++/13/bits/stl_pair.h:90:11: note: 'std::tuple' declared here
   90 |     class tuple;
      |           ^~~~~
dreaming.cpp:79:5: error: 'forward_list' was not declared in this scope
   79 |     forward_list<tuple<int, bool> > height_calculation;
      |     ^~~~~~~~~~~~
dreaming.cpp:79:5: note: suggested alternatives:
/usr/include/c++/13/bits/forward_list.h:433:11: note:   'std::forward_list'
  433 |     class forward_list : private _Fwd_list_base<_Tp, _Alloc>
      |           ^~~~~~~~~~~~
/usr/include/c++/13/forward_list:56:13: note:   'std::pmr::forward_list'
   56 |       using forward_list = std::forward_list<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~~~~~~~
dreaming.cpp:79:24: error: expected primary-expression before 'int'
   79 |     forward_list<tuple<int, bool> > height_calculation;
      |                        ^~~
dreaming.cpp:81:9: error: 'height_calculation' was not declared in this scope
   81 |         height_calculation.push_front(make_tuple(root_vertices[i], false));
      |         ^~~~~~~~~~~~~~~~~~
dreaming.cpp:81:39: error: 'make_tuple' was not declared in this scope; did you mean 'std::make_tuple'?
   81 |         height_calculation.push_front(make_tuple(root_vertices[i], false));
      |                                       ^~~~~~~~~~
      |                                       std::make_tuple
In file included from /usr/include/c++/13/bits/uses_allocator_args.h:38,
                 from /usr/include/c++/13/bits/memory_resource.h:41,
                 from /usr/include/c++/13/vector:80:
/usr/include/c++/13/tuple:2001:5: note: 'std::make_tuple' declared here
 2001 |     make_tuple(_Elements&&... __args)
      |     ^~~~~~~~~~
dreaming.cpp:83:12: error: 'height_calculation' was not declared in this scope
   83 |     while(!height_calculation.empty()){
      |            ^~~~~~~~~~~~~~~~~~
dreaming.cpp:86:9: error: 'tie' was not declared in this scope; did you mean 'std::tie'?
   86 |         tie(vertex, status) = height_calculation.front();
      |         ^~~
      |         std::tie
/usr/include/c++/13/tuple:2169:5: note: 'std::tie' declared here
 2169 |     tie(_Elements&... __args) noexcept
      |     ^~~
dreaming.cpp:89:28: error: 'child_edges' was not declared in this scope
   89 |             for(int edge : child_edges[vertex]){
      |                            ^~~~~~~~~~~
dreaming.cpp:97:43: error: 'make_tuple' was not declared in this scope; did you mean 'std::make_tuple'?
   97 |             height_calculation.push_front(make_tuple(vertex, true));
      |                                           ^~~~~~~~~~
      |                                           std::make_tuple
/usr/include/c++/13/tuple:2001:5: note: 'std::make_tuple' declared here
 2001 |     make_tuple(_Elements&&... __args)
      |     ^~~~~~~~~~
dreaming.cpp:98:28: error: 'child_edges' was not declared in this scope
   98 |             for(int edge : child_edges[vertex]){
      |                            ^~~~~~~~~~~
dreaming.cpp:103:5: error: 'vector' was not declared in this scope
  103 |     vector<int> max_paths[N - M];
      |     ^~~~~~
dreaming.cpp:103:5: note: suggested alternatives:
In file included from /usr/include/c++/13/vector:66:
/usr/include/c++/13/bits/stl_vector.h:428:11: note:   'std::vector'
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
/usr/include/c++/13/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
dreaming.cpp:103:12: error: expected primary-expression before 'int'
  103 |     vector<int> max_paths[N - M];
      |            ^~~
dreaming.cpp:106:9: error: 'max_paths' was not declared in this scope
  106 |         max_paths[component] = {root};
      |         ^~~~~~~~~
dreaming.cpp:112:13: error: 'child_edges' was not declared in this scope
  112 |             child_edges[last_vertex].erase(height_edges[last_vertex]);
      |             ^~~~~~~~~~~
dreaming.cpp:117:25: error: 'max_paths' was not declared in this scope
  117 |         int best_upward[max_paths[component].size()];
      |                         ^~~~~~~~~
dreaming.cpp:118:9: error: 'best_upward' was not declared in this scope
  118 |         best_upward[0] = 0;
      |         ^~~~~~~~~~~
dreaming.cpp:121:28: error: 'child_edges' was not declared in this scope
  121 |             for(int edge : child_edges[max_paths[component][i]]){
      |                            ^~~~~~~~~~~
dreaming.cpp:130:18: error: expected primary-expression before 'int'
  130 |     forward_list<int> eccentricity_calculation;
      |                  ^~~
dreaming.cpp:131:16: error: expected primary-expression before 'int'
  131 |     for(vector<int> max_path : max_paths){
      |                ^~~
dreaming.cpp:136:5: error: expected primary-expression before 'while'
  136 |     while(!eccentricity_calculation.empty()){
      |     ^~~~~
dreaming.cpp:135:6: error: expected ';' before 'while'
  135 |     }
      |      ^
      |      ;
  136 |     while(!eccentricity_calculation.empty()){
      |     ~~~~~
dreaming.cpp:136:5: error: expected primary-expression before 'while'
  136 |     while(!eccentricity_calculation.empty()){
      |     ^~~~~
dreaming.cpp:135:6: error: expected ')' before 'while'
  135 |     }
      |      ^
      |      )
  136 |     while(!eccentricity_calculation.empty()){
      |     ~~~~~
dreaming.cpp:131:8: note: to match this '('
  131 |     for(vector<int> max_path : max_paths){
      |        ^
dreaming.cpp:136:12: error: 'eccentricity_calculation' was not declared in this scope
  136 |     while(!eccentricity_calculation.empty()){
      |            ^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:139:24: error: 'child_edges' was not declared in this scope
  139 |         for(int edge : child_edges[vertex]){
      |                        ^~~~~~~~~~~