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 <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <cassert>
using namespace std;
vector<vector<int> > adj;
vector<int> sub, ans;
int dfs(int a, int p) {
sub[a] = 0;
for(int b : adj[a]) if(b != p) {
sub[a] += dfs(b, a);
}
return sub[a];
}
void dfs2(int a, vector<int> & ans, int color) {
ans[a] = color;
for(int b : adj[a]) if(sub[b] < sub[a]) {
dfs2(b, ans, color);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
adj.resize(n);
ans.assign(n, 0);
for(int i = 0; i < (int)p.size(); i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
bool two_endpoints = true;
for(int i = 0; i < n; i++) {
if(adj[i].size() > 2) two_endpoints = false;
}
vector<pair<int,int> > colors;
colors.push_back(make_pair(a, 1));
colors.push_back(make_pair(b, 2));
colors.push_back(make_pair(c, 3));
sort(colors.begin(), colors.end());
if(two_endpoints) {
for(int i = 0; i < n; i++) {
if(a > 0) { ans[i] = 1; a--; }
else if(b > 0) { ans[i] = 2; b--; }
else if(c > 0) { ans[i] = 3; c--; }
}
return ans;
} else if(p.size() == n - 1) { // tree
sub.resize(n);
dfs(0, 0);
int possible = -1;
int smallest = colors[0].first;
int medium = colors[1].first;
for(int i = 0; i < n && possible == -1; i++) {
if(sub[i] >= smallest && n - sub[i] >= medium) {
possible = i;
} else if(sub[i] >= medium && n - sub[i] >= smallest) {
assert(false); // Why the fuck would this happen?
possible = i;
}
}
if(possible != -1) {
dfs2(possible, ans, colors[0].second);
dfs2(possible, ans, colors[1].second);
for(int i = 0; i < n; i++) if(ans[i] == 0) {
ans[i] = colors[2].second;
}
}
return ans;
} else if(true || a == 1) {
return ans;
}
}
int _main() {
int n, m, a, b, c;
cin >> n >> m >> a >> b >> c;
vector<int> p(m), pp(m);
for(int i = 0; i < m; i++) {
cin >> p[i] >> pp[i];
}
vector<int> _ans = find_split(n, a, b, c, p, pp);
for(int x : _ans) {
cout << x << " ";
}
cout << endl;
return 0;
}
Compilation message (stderr)
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:54:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
54 | } else if(p.size() == n - 1) { // tree
| ~~~~~~~~~^~~~~~~~
# | 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... |