Submission #290406

#	Time	Username	Problem	Language	Result	Execution time	Memory
290406		A02	Simurgh (IOI17_simurgh)	C++14	51 / 100	225 ms	3712 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

vector<int> find_roads(int n, vector<int> u, vector<int> v) {

	vector<vector<pair<int, int> > > adjacent (n, vector<pair<int, int> >());

	for (int i = 0; i < u.size(); i++){
        adjacent[u[i]].push_back(make_pair(v[i], i));
        adjacent[v[i]].push_back(make_pair(u[i], i));
	}

	int m = u.size();

	vector<int> decided (m, -1);

	for (int i = 0; i < n; i++){

        vector<int> established_tree;

        vector<int> region (n, -1);
        region[i] = -2;
        int c_region = 0;

        for (int a = 0; a < n; a++){

            if (a != i){
                if (region[a] == -1){

                    region[a] = c_region;

                    queue<int> to_visit;
                    to_visit.push(a);

                    while (!to_visit.empty()){

                        int current = to_visit.front();
                        to_visit.pop();

                        for (int j = 0; j < adjacent[current].size(); j++){
                            int next = adjacent[current][j].first;
                            if (region[next] == -1){
                                established_tree.push_back(adjacent[current][j].second);
                                to_visit.push(next);
                                region[next] = c_region;
                            }
                        }

                    }

                    c_region++;
                }
            }
        }


        vector<vector<int> > possible_additional_edges (c_region, vector<int>());

        vector<int> reference_set (c_region, -1);
        vector<int> reference_value (c_region, -1);

        for (int j = 0; j < adjacent[i].size(); j++){
            int adjacent_vertex = adjacent[i][j].first;
            int edge_label = adjacent[i][j].second;
            int v_region = region[adjacent_vertex];

            possible_additional_edges[v_region].push_back(edge_label);

            if (decided[edge_label] != -1 && reference_set[v_region] == -1){
                reference_set[v_region] = edge_label;
                reference_value[v_region] = decided[edge_label];
            }
        }

        for (int r = 0; r < c_region; r++){
            if (reference_set[r] == -1){
                reference_set[r] = possible_additional_edges[r][0];
            }
        }

        vector<int> full_reference_set = established_tree;
        for (int j = 0; j < c_region; j++){
            full_reference_set.push_back(reference_set[j]);
        }

        int reference_total = count_common_roads(full_reference_set);

        for (int r = 0; r < c_region; r++){
            int current_reference_value = reference_value[r];
            vector<int> current_set = full_reference_set;
            current_set.erase(find(current_set.begin(), current_set.end(), reference_set[r]));

            if (current_reference_value != -1){
                for (int j = 0; j < possible_additional_edges[r].size(); j++){
                    int current_edge = possible_additional_edges[r][j];
                    if (decided[current_edge] == -1){
                        current_set.push_back(current_edge);
                        int new_total = count_common_roads(current_set);
                        current_set.pop_back();

                        if (new_total == reference_total){
                            decided[current_edge] = current_reference_value;
                        } else {
                            if (current_reference_value == 0){
                                decided[current_edge] = 1;
                            } else{
                                decided[current_edge] = 0;
                            }
                        }
                    }
                }
            } else {
                vector<int> values_region_r (possible_additional_edges[r].size(), 0);

                if (possible_additional_edges[r].size() == 1){
                    decided[possible_additional_edges[r][0]] = 1;
                } else{

                    for (int j = 0; j < possible_additional_edges[r].size(); j++){
                        current_set.push_back(possible_additional_edges[r][j]);
                        values_region_r[j] = count_common_roads(current_set);
                        current_set.pop_back();
                    }

                    int upper = *max_element(values_region_r.begin(), values_region_r.end());

                    for (int j = 0; j < possible_additional_edges[r].size(); j++){
                        if (values_region_r[j] == upper){
                            decided[possible_additional_edges[r][j]] = 1;
                        } else {
                            decided[possible_additional_edges[r][j]] = 0;
                        }
                    }
                }
            }

        }
	}

    vector<int> answer;
    for (int i = 0; i < decided.size(); i++){
        if (decided[i] == 1){
            answer.push_back(i);
        }
    }

	return answer;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:10:20: 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 < u.size(); i++){
      |                  ~~^~~~~~~~~~
simurgh.cpp:42:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                         for (int j = 0; j < adjacent[current].size(); j++){
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int j = 0; j < adjacent[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~
simurgh.cpp:96:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 for (int j = 0; j < possible_additional_edges[r].size(); j++){
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:121:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |                     for (int j = 0; j < possible_additional_edges[r].size(); j++){
      |                                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:129:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                     for (int j = 0; j < possible_additional_edges[r].size(); j++){
      |                                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i = 0; i < decided.size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30