#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
struct tree {
int n;
vector <int> weight, dad;
vector <vector <pii>> adj;
tree() {
n = 0;
}
int add_node() {
weight.push_back(0);
dad.push_back(-1);
adj.push_back({});
return n++;
}
void add_edge(int x, int y) {
//printf("adding to block cut tree %d %d\n", x, y);
adj[x].push_back({y, 0});
adj[y].push_back({x, 0});
}
void set_weight(int x, int w) {
weight[x] = w;
}
void calc(int x, int p) {
dad[x] = p;
for (auto &it : adj[x])
if (it.first != p) {
calc(it.first, x);
weight[x] += weight[it.first];
it.second = weight[it.first];
}
}
int centroid() {
for (int i = 0; i < n; i++) {
int mx = 0;
for (auto &it : adj[i]) {
if (it.first == dad[i])
it.second = weight[0] - weight[i];
mx = max(mx, it.second);
}
if (mx <= weight[0] / 2)
return i;
}
assert(false);
}
void go(int x, int p, vector <int> &v) {
v.push_back(x);
for (auto it : adj[x])
if (it.first != p)
go(it.first, x, v);
}
};
struct graph {
int n, timer;
vector <vector <int>> adj;
vector <int> disc, low;
vector <int> dad, link;
vector <vector <int>> comps;
vector <vector <int>> memo, group;
vector <int> preorder;
stack <int> stk;
vector <bool> art;
vector <int> idx;
graph(int _n) {
n = _n;
timer = 0;
disc.resize(n);
low.resize(n);
dad.resize(n);
link.resize(n);
art.resize(n);
idx.resize(n);
adj.resize(n);
memo.resize(n);
group.resize(n);
for (int i = 0; i < n; i++)
group[i] = {i};
}
graph(){}
void add_edge(int x, int y) {
adj[x].push_back(y);
adj[y].push_back(x);
}
void dfs(int x, int p) {
preorder.push_back(x);
disc[x] = low[x] = ++timer;
link[x] = x;
dad[x] = p;
stk.push(x);
for (auto it : adj[x])
if (!disc[it]) {
dfs(it, x);
if (low[it] < low[x]) {
low[x] = low[it];
link[x] = it;
}
if (low[it] >= disc[x]) {
art[x] = disc[x] > 1 || disc[it] > 2;
comps.push_back({x});
for (; comps.back().back() != it; stk.pop())
comps.back().push_back(stk.top());
}
}
else if (it != p && disc[it] < low[x]) {
low[x] = disc[it];
link[x] = it;
}
}
tree block_cut() {
tree res;
for (int i = 0; i < n; i++)
if (art[i]) {
idx[i] = res.add_node();
res.set_weight(idx[i], 1);
memo[idx[i]] = {i};
}
for (auto comp : comps) {
int node = res.add_node();
int sz = comp.size();
memo[node] = comp;
for (auto it : comp)
if (art[it]) {
res.add_edge(node, idx[it]);
sz--;
}
res.set_weight(node, sz);
}
return res;
}
vector <int> st_numbering() {
vector <int> prv(n, -1), nxt(n, -1), sgn(n, -1);
sgn[0] = 0;
for (auto it : preorder) {
if (sgn[link[it]]) {
sgn[dad[it]] = 0;
if (nxt[dad[it]] != -1)
prv[nxt[dad[it]]] = it;
nxt[it] = nxt[dad[it]];
prv[it] = dad[it];
nxt[dad[it]] = it;
}
else {
sgn[dad[it]] = 1;
if (prv[dad[it]] != -1)
nxt[prv[dad[it]]] = it;
prv[it] = prv[dad[it]];
nxt[it] = dad[it];
prv[dad[it]] = it;
}
}
vector <int> res;
for (int x = 0; x != -1; x = nxt[x])
res.push_back(x);
return res;
}
graph induced(const vector <int> &subset) {
vector <int> label(n, -1);
int sz = subset.size();
for (int i = 0; i < sz; i++)
label[subset[i]] = i;
graph res(sz);
for (int i = 0; i < sz; i++)
for (auto it : adj[subset[i]])
if (label[it] != -1)
res.add_edge(i, label[it]);
return res;
}
vector <int> clip(int num) {
dfs(0, -1);
preorder.resize(num);
return preorder;
}
vector <int> construct(const vector <int> &subset, const vector <pii> &p) {
vector <bool> in(n, false);
for (auto it : subset)
in[it] = true;
vector <int> rest;
for (int i = 0; i < n; i++)
if (!in[i])
rest.push_back(i);
vector <int> A = induced(subset).clip(p[0].first);
vector <int> B = induced(rest).clip(p[1].first);
vector <int> res(n, p[2].second);
for (auto it : A)
res[subset[it]] = p[0].second;
for (auto it : B)
res[rest[it]] = p[1].second;
return res;
}
};
graph G, H;
tree T;
void output(const vector <int> &v) {
for (auto it : v)
printf("%d ", it);
puts("");
}
vector <int> find_split(int N, int a, int b, int c, vector <int> u, vector <int> v) {
vector <pii> parts = {{a, 1}, {b, 2}, {c, 3}};
sort(parts.begin(), parts.end());
G = graph(N);
for (int i = 0; i < u.size(); i++)
G.add_edge(u[i], v[i]);
G.dfs(0, -1);
T = G.block_cut();
T.calc(0, -1);
int node = T.centroid();
//printf("centroid %d\n", node);
//printf("sajz %d\n", T.adj[node].size());
bool single = G.memo[node].size() == 1;
for (auto it : T.adj[node]) {
//printf("neighbour size %d %d\n", it.first, it.second);
vector <int> branch;
T.go(it.first, node, branch);
//output(branch);
vector <int> tmp;
for (auto it1 : branch)
for (auto it2 : G.memo[it1])
if (!single || it2 != G.memo[node][0])
tmp.push_back(it2);
sort(tmp.begin(), tmp.end());
tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
//output(tmp);
assert(tmp.size() == it.second);
G.group[G.memo[it.first][0]] = tmp;
if (it.second >= parts[0].first)
return G.construct(tmp, parts);
}
if (single)
return vector <int> (N, 0);
H = G.induced(G.memo[node]);
vector <int> order = H.st_numbering();
vector <int> lft;
for (auto it : order) {
int tmp = G.memo[node][it];
for (auto it1 : G.group[tmp])
lft.push_back(it1);
if (lft.size() >= parts[0].first)
return G.construct(lft, parts);
}
return {};
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:236:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < u.size(); i++)
~~^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from split.cpp:1:
split.cpp:262:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(tmp.size() == it.second);
~~~~~~~~~~~^~~~~~~
split.cpp:278:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (lft.size() >= parts[0].first)
~~~~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
ok, correct split |
| 2 |
Correct |
2 ms |
252 KB |
ok, correct split |
| 3 |
Runtime error |
2 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
ok, correct split |
| 2 |
Correct |
2 ms |
256 KB |
ok, correct split |
| 3 |
Correct |
2 ms |
252 KB |
ok, correct split |
| 4 |
Correct |
313 ms |
48808 KB |
ok, correct split |
| 5 |
Runtime error |
190 ms |
65000 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
ok, correct split |
| 2 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
| 3 |
Correct |
2 ms |
256 KB |
ok, correct split |
| 4 |
Correct |
2 ms |
256 KB |
ok, correct split |
| 5 |
Incorrect |
2 ms |
256 KB |
WA in grader: Invalid length of the result. |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
ok, correct split |
| 2 |
Correct |
2 ms |
252 KB |
ok, correct split |
| 3 |
Runtime error |
2 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
