제출 #297515

#제출 시각아이디문제언어결과실행 시간메모리
297515A02Split the Attractions (IOI19_split)C++14
0 / 100
2064 ms8696 KiB
#include <bits/stdc++.h> #include "split.h" using namespace std; void root_tree(vector<vector<int> > &adjacent, int current, vector<int> &parents){ for (int i = 0; i < adjacent[current].size(); i++){ int child = adjacent[current][i]; if (child != parents[current]){ parents[child] = current; root_tree(adjacent, child, parents); } } } void calc_subtree_sizes(vector<vector<int> > &adjacent, int current, vector<int> &parents, vector<int> &subtree_sizes){ for (int i = 0; i < adjacent[current].size(); i++){ int child = adjacent[current][i]; if (child != parents[current]){ calc_subtree_sizes(adjacent, child, parents, subtree_sizes); subtree_sizes[current] += subtree_sizes[child]; } } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m = q.size(); vector<pair<int, int> > sets; sets.push_back(make_pair(a, 1)); sets.push_back(make_pair(b, 2)); sets.push_back(make_pair(c, 3)); sort(sets.begin(), sets.end()); a = sets[0].first; b = sets[1].first; c = sets[2].first; vector<int> res (n, sets[2].second); vector<vector<int> > adjacent (n, vector<int>()); for (int i = 0; i < p.size(); i++){ adjacent[p[i]].push_back(q[i]); adjacent[q[i]].push_back(p[i]); } if (m == n - 1){ vector<int> parents (n, -1); vector<int> subtree_sizes (n, 1); root_tree(adjacent, 0, parents); calc_subtree_sizes(adjacent, 0, parents, subtree_sizes); for (int i = 0; i < n; i++){ vector<pair<int, int> > i_subtree_sizes; if (i != 0){ i_subtree_sizes.push_back(make_pair(n - subtree_sizes[i], parents[i])); } for (int j = 0; j < adjacent[i].size(); j++){ int child = adjacent[i][j]; i_subtree_sizes.push_back(make_pair(subtree_sizes[child], child)); } for (int k = 0; k < i_subtree_sizes.size(); k++){ int s_size = i_subtree_sizes[k].first; if (s_size >= b && n - s_size >= a){ queue<int> b_to_visit; b_to_visit.push(i_subtree_sizes[k].second); res[i_subtree_sizes[k].second] = sets[1].second; res[i] = sets[0].second; int b_size = 1; while (b_size < b){ int current = b_to_visit.front(); for (int j = 0; j < adjacent[current].size(); j++){ int next = adjacent[current][j]; if (res[next] == sets[2].second && b_size < b){ b_size++; res[next] = sets[1].second; b_to_visit.push(next); } } } queue<int> a_to_visit; a_to_visit.push(i); int a_size = 1; while (a_size < a){ int current = a_to_visit.front(); for (int j = 0; j < adjacent[current].size(); j++){ int next = adjacent[current][j]; if (res[next] == sets[2].second && a_size < a){ a_size++; res[next] = sets[0].second; a_to_visit.push(next); } } } return res; } } } return vector<int> (n, 0); } }

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'void root_tree(std::vector<std::vector<int> >&, int, std::vector<int>&)':
split.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i = 0; i < adjacent[current].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'void calc_subtree_sizes(std::vector<std::vector<int> >&, int, std::vector<int>&, std::vector<int>&)':
split.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < adjacent[current].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < p.size(); i++){
      |                  ~~^~~~~~~~~~
split.cpp:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for (int j = 0; j < adjacent[i].size(); j++){
      |                             ~~^~~~~~~~~~~~~~~~~~~~
split.cpp:73:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for (int k = 0; k < i_subtree_sizes.size(); k++){
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:91:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                         for (int j = 0; j < adjacent[current].size(); j++){
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:112:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                         for (int j = 0; j < adjacent[current].size(); j++){
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:33:26: warning: control reaches end of non-void function [-Wreturn-type]
   33 |  vector<pair<int, int> > sets;
      |                          ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...