Submission #1280994

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

dreaming

#include "dreaming.h"

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:27:5: error: 'unordered_set' was not declared in this scope
   27 |     unordered_set<int> child_edges[N];
      |     ^~~~~~~~~~~~~
dreaming.cpp:27:19: error: expected primary-expression before 'int'
   27 |     unordered_set<int> child_edges[N];
      |                   ^~~
dreaming.cpp:33:9: error: 'child_edges' was not declared in this scope
   33 |         child_edges[A[i]].insert(i);
      |         ^~~~~~~~~~~
dreaming.cpp:40:46: error: 'child_edges' was not declared in this scope
   40 |         if(components[current_root] != -1 || child_edges[current_root].size() > 1){
      |                                              ^~~~~~~~~~~
dreaming.cpp:44:12: error: 'child_edges' was not declared in this scope
   44 |         if(child_edges[current_root].empty()){
      |            ^~~~~~~~~~~
dreaming.cpp:52:9: error: 'forward_list' was not declared in this scope
   52 |         forward_list<int> children = {current_root};
      |         ^~~~~~~~~~~~
dreaming.cpp:52:22: error: expected primary-expression before 'int'
   52 |         forward_list<int> children = {current_root};
      |                      ^~~
dreaming.cpp:53:16: error: 'children' was not declared in this scope
   53 |         while(!children.empty()){
      |                ^~~~~~~~
dreaming.cpp:57:28: error: 'child_edges' was not declared in this scope
   57 |             for(int edge : child_edges[child]){
      |                            ^~~~~~~~~~~
dreaming.cpp:74:18: error: 'tuple' was not declared in this scope
   74 |     forward_list<tuple<int, bool> > height_calculation;
      |                  ^~~~~
dreaming.cpp:74:5: error: 'forward_list' was not declared in this scope
   74 |     forward_list<tuple<int, bool> > height_calculation;
      |     ^~~~~~~~~~~~
dreaming.cpp:74:24: error: expected primary-expression before 'int'
   74 |     forward_list<tuple<int, bool> > height_calculation;
      |                        ^~~
dreaming.cpp:76:9: error: 'height_calculation' was not declared in this scope
   76 |         height_calculation.push_front(make_tuple(root_vertices[i], false));
      |         ^~~~~~~~~~~~~~~~~~
dreaming.cpp:76:39: error: 'make_tuple' was not declared in this scope
   76 |         height_calculation.push_front(make_tuple(root_vertices[i], false));
      |                                       ^~~~~~~~~~
dreaming.cpp:78:12: error: 'height_calculation' was not declared in this scope
   78 |     while(!height_calculation.empty()){
      |            ^~~~~~~~~~~~~~~~~~
dreaming.cpp:81:9: error: 'tie' was not declared in this scope
   81 |         tie(vertex, status) = height_calculation.front();
      |         ^~~
dreaming.cpp:84:28: error: 'child_edges' was not declared in this scope
   84 |             for(int edge : child_edges[vertex]){
      |                            ^~~~~~~~~~~
dreaming.cpp:92:43: error: 'make_tuple' was not declared in this scope
   92 |             height_calculation.push_front(make_tuple(vertex, true));
      |                                           ^~~~~~~~~~
dreaming.cpp:93:28: error: 'child_edges' was not declared in this scope
   93 |             for(int edge : child_edges[vertex]){
      |                            ^~~~~~~~~~~
dreaming.cpp:98:5: error: 'vector' was not declared in this scope
   98 |     vector<int> max_paths[N - M];
      |     ^~~~~~
dreaming.cpp:98:12: error: expected primary-expression before 'int'
   98 |     vector<int> max_paths[N - M];
      |            ^~~
dreaming.cpp:101:9: error: 'max_paths' was not declared in this scope
  101 |         max_paths[component] = {root};
      |         ^~~~~~~~~
dreaming.cpp:107:13: error: 'child_edges' was not declared in this scope
  107 |             child_edges[last_vertex].erase(height_edges[last_vertex]);
      |             ^~~~~~~~~~~
dreaming.cpp:112:25: error: 'max_paths' was not declared in this scope
  112 |         int best_upward[max_paths[component].size()];
      |                         ^~~~~~~~~
dreaming.cpp:113:9: error: 'best_upward' was not declared in this scope
  113 |         best_upward[0] = 0;
      |         ^~~~~~~~~~~
dreaming.cpp:116:28: error: 'child_edges' was not declared in this scope
  116 |             for(int edge : child_edges[max_paths[component][i]]){
      |                            ^~~~~~~~~~~
dreaming.cpp:125:18: error: expected primary-expression before 'int'
  125 |     forward_list<int> eccentricity_calculation;
      |                  ^~~
dreaming.cpp:126:16: error: expected primary-expression before 'int'
  126 |     for(vector<int> max_path : max_paths){
      |                ^~~
dreaming.cpp:131:5: error: expected primary-expression before 'while'
  131 |     while(!eccentricity_calculation.empty()){
      |     ^~~~~
dreaming.cpp:130:6: error: expected ';' before 'while'
  130 |     }
      |      ^
      |      ;
  131 |     while(!eccentricity_calculation.empty()){
      |     ~~~~~
dreaming.cpp:131:5: error: expected primary-expression before 'while'
  131 |     while(!eccentricity_calculation.empty()){
      |     ^~~~~
dreaming.cpp:130:6: error: expected ')' before 'while'
  130 |     }
      |      ^
      |      )
  131 |     while(!eccentricity_calculation.empty()){
      |     ~~~~~
dreaming.cpp:126:8: note: to match this '('
  126 |     for(vector<int> max_path : max_paths){
      |        ^
dreaming.cpp:131:12: error: 'eccentricity_calculation' was not declared in this scope
  131 |     while(!eccentricity_calculation.empty()){
      |            ^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:134:24: error: 'child_edges' was not declared in this scope
  134 |         for(int edge : child_edges[vertex]){
      |                        ^~~~~~~~~~~