이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
//cout << s_size << ' ' << b << endl;
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);
}
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++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |