| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 290403 |
2020-09-03T18:00:15 Z |
A02 |
Simurgh (IOI17_simurgh) |
C++14 |
|
171 ms |
3912 KB |
#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> partial_set;
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] && reference_set[v_region] == -1){
reference_set[v_region] = edge_label;
reference_value[decided[edge_label]] = v_region;
}
}
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
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:43: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]
43 | for (int j = 0; j < adjacent[current].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:65: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]
65 | for (int j = 0; j < adjacent[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~
simurgh.cpp:97:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int j = 0; j < possible_additional_edges[r].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:122:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int j = 0; j < possible_additional_edges[r].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:130:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for (int j = 0; j < possible_additional_edges[r].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (int i = 0; i < decided.size(); i++){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
correct |
| 2 |
Correct |
0 ms |
256 KB |
correct |
| 3 |
Correct |
0 ms |
256 KB |
correct |
| 4 |
Correct |
1 ms |
256 KB |
correct |
| 5 |
Correct |
1 ms |
256 KB |
correct |
| 6 |
Correct |
1 ms |
256 KB |
correct |
| 7 |
Correct |
0 ms |
256 KB |
correct |
| 8 |
Correct |
1 ms |
256 KB |
correct |
| 9 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
correct |
| 2 |
Correct |
0 ms |
256 KB |
correct |
| 3 |
Correct |
0 ms |
256 KB |
correct |
| 4 |
Correct |
1 ms |
256 KB |
correct |
| 5 |
Correct |
1 ms |
256 KB |
correct |
| 6 |
Correct |
1 ms |
256 KB |
correct |
| 7 |
Correct |
0 ms |
256 KB |
correct |
| 8 |
Correct |
1 ms |
256 KB |
correct |
| 9 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
correct |
| 2 |
Correct |
0 ms |
256 KB |
correct |
| 3 |
Correct |
0 ms |
256 KB |
correct |
| 4 |
Correct |
1 ms |
256 KB |
correct |
| 5 |
Correct |
1 ms |
256 KB |
correct |
| 6 |
Correct |
1 ms |
256 KB |
correct |
| 7 |
Correct |
0 ms |
256 KB |
correct |
| 8 |
Correct |
1 ms |
256 KB |
correct |
| 9 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
correct |
| 2 |
Correct |
1 ms |
256 KB |
correct |
| 3 |
Incorrect |
171 ms |
3912 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
correct |
| 2 |
Correct |
0 ms |
256 KB |
correct |
| 3 |
Correct |
0 ms |
256 KB |
correct |
| 4 |
Correct |
1 ms |
256 KB |
correct |
| 5 |
Correct |
1 ms |
256 KB |
correct |
| 6 |
Correct |
1 ms |
256 KB |
correct |
| 7 |
Correct |
0 ms |
256 KB |
correct |
| 8 |
Correct |
1 ms |
256 KB |
correct |
| 9 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 |
| 10 |
Halted |
0 ms |
0 KB |
- |
