#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 (parents[child] == 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){
int current = 0;
int a_size = 1;
int b_size = 0;
res[current] = sets[0].second;
while (a_size < a){
if (res[adjacent[current][0]] == sets[2].second){
current = adjacent[current][0];
res[current] = sets[0].second;
} else {
current = adjacent[current][1];
res[current] = sets[0].second;
}
a_size++;
}
while (b_size < b){
if (res[adjacent[current][0]] == sets[2].second){
current = adjacent[current][0];
res[current] = sets[1].second;
} else {
current = adjacent[current][1];
res[current] = sets[1].second;
}
b_size++;
}
return res;
}
if (a == 1){
queue<int> to_visit;
int b_size = 1;
res[0] = sets[1].second;
to_visit.push(0);
while(b_size < b){
int current = to_visit.front();
to_visit.pop();
for (int i = 0; i < adjacent[current].size(); i++){
int next = adjacent[current][i];
if (res[next] == sets[2].second){
res[next] = sets[1].second;
b_size++;
to_visit.push(next);
}
}
}
for (int i = 0; i < n; i++){
if (res[i] == sets[2].second){
res[i] = sets[0].second;
break;
}
}
return res;
}
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();
b_to_visit.pop();
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();
a_to_visit.pop();
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);
}
Compilation message
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:97:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i = 0; i < adjacent[current].size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:135:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int j = 0; j < adjacent[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~
split.cpp:140: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]
140 | for (int k = 0; k < i_subtree_sizes.size(); k++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:160:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for (int j = 0; j < adjacent[current].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
split.cpp:182:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for (int j = 0; j < adjacent[current].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
ok, correct split |
| 2 |
Correct |
0 ms |
256 KB |
ok, correct split |
| 3 |
Correct |
1 ms |
256 KB |
ok, correct split |
| 4 |
Correct |
1 ms |
256 KB |
ok, correct split |
| 5 |
Correct |
1 ms |
256 KB |
ok, correct split |
| 6 |
Correct |
0 ms |
256 KB |
ok, correct split |
| 7 |
Correct |
138 ms |
15992 KB |
ok, correct split |
| 8 |
Incorrect |
70 ms |
7800 KB |
invalid split: #1=1, #2=99996, #3=3 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
ok, correct split |
| 2 |
Correct |
1 ms |
360 KB |
ok, correct split |
| 3 |
Correct |
0 ms |
256 KB |
ok, correct split |
| 4 |
Correct |
98 ms |
8844 KB |
ok, correct split |
| 5 |
Incorrect |
118 ms |
7904 KB |
invalid split: #1=1, #2=50002, #3=49996 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
invalid split: #1=3, #2=1, #3=1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
256 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
ok, correct split |
| 2 |
Correct |
0 ms |
256 KB |
ok, correct split |
| 3 |
Correct |
1 ms |
256 KB |
ok, correct split |
| 4 |
Correct |
1 ms |
256 KB |
ok, correct split |
| 5 |
Correct |
1 ms |
256 KB |
ok, correct split |
| 6 |
Correct |
0 ms |
256 KB |
ok, correct split |
| 7 |
Correct |
138 ms |
15992 KB |
ok, correct split |
| 8 |
Incorrect |
70 ms |
7800 KB |
invalid split: #1=1, #2=99996, #3=3 |
| 9 |
Halted |
0 ms |
0 KB |
- |
