This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
vector<vector<int>> graph(n);
for (int i = 0; i < q.size(); i++) {
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
vector<int> ans(n, 0);
vector<int> component(n, -1);
vector<int> size;
function<void(int, int)> dfs = [&](int u, int comp_id) {
component[u] = comp_id;
size[comp_id]++;
for (int v : graph[u]) {
if (component[v] == -1) {
dfs(v, comp_id);
}
}
};
int comp_count = 0;
for (int i = 0; i < n; i++) {
if (component[i] == -1) {
size.push_back(0);
dfs(i, comp_count++);
}
}
vector<int> order(comp_count);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int x, int y) {
return size[x] > size[y];
});
if (size[order[0]] >= b + c) {
int remaining = b + c;
queue<int> q;
q.push(-1);
for (int i = 0; i < n; i++) {
if (component[i] == order[0]) {
if (remaining > c) {
ans[i] = 2;
remaining--;
} else {
ans[i] = 3;
}
}
}
if (remaining != 0) {
return vector<int>(n, 0);
}
} else {
int remaining_b = b, remaining_c = c;
for (int id : order) {
if (size[id] <= remaining_b && remaining_b > 0) {
for (int i = 0; i < n; i++) {
if (component[i] == id) {
ans[i] = 2;
remaining_b--;
}
}
} else {
for (int i = 0; i < n; i++) {
if (component[i] == id && remaining_c > 0) {
ans[i] = 3;
remaining_c--;
}
}
}
}
if (remaining_b != 0 || remaining_c != 0) {
return vector<int>(n, 0);
}
}
int remaining_a = a;
for (int i = 0; i < n; i++) {
if (ans[i] == 0 && remaining_a > 0) {
ans[i] = 1;
remaining_a--;
}
}
if (remaining_a != 0) {
return vector<int>(n, 0);
}
return ans;
}
Compilation message (stderr)
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | for (int i = 0; i < q.size(); i++) {
| ~~^~~~~~~~~~
# | 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... |