#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#include "sphinx.h"
//#include "grader.cpp"
#define sz(x) int(x.size())
int n, mmo;
int p[255], sz[255], p2[255], sz2[255], dep[255], idxo = 1;
vector<int> adj57[255], tr[255], bck[255], adj2[255], nds[255], ret;
int vis[255];
bool fnd[255];
vector<int> fo, so;
int findp2(int u) {
return p2[u] = (p2[u] == u ? u : findp2(p2[u]));
}
bool merge2(int u, int v) {
u = findp2(u), v = findp2(v);
if (u == v)return false;
if (sz2[u] < sz2[v])swap(u, v);
sz2[u] += sz2[v];
p2[v] = u;
return true;
}
int findp(int u) {
return p[u] = (p[u] == u ? u : findp(p[u]));
}
void merge(int u, int v) {
u = findp(u), v = findp(v);
if (u == v)return;
if (sz[u] < sz[v])swap(u, v);
sz[u] += sz[v];
p[v] = u;
}
bool chk(vector<int> v) {
for (int i = 0; i < n; i++) {
p2[i] = i;
sz2[i] = 1;
}
int comps = n;
for (int i = 0; i < n; i++) {
for (auto &vv : adj57[i]) {
if (~v[i] && v[i] == v[vv]) {
comps -= merge2(i, vv);
} else if (v[i] == -1 && v[vv] == -1 && findp(i) == findp(vv)) {
comps -= merge2(i, vv);
}
}
}
int x = perform_experiment(v);
return (comps > x);
}
bool chk2(int u, int v) {
for (int i = 0; i < n; i++) {
p2[i] = i;
sz2[i] = 1;
}
int comps = n;
vector<int> e(n, n);
e[u] = e[v] = -1;
for (int i = 0; i < n; i++) {
for (auto &vv : adj57[i]) {
if (e[i] == e[vv]) {
comps -= merge2(i, vv);
}
}
}
int x = perform_experiment(e);
return (comps == x);
}
void init(int u, int pr) {
vis[u] = idxo++;
for (auto &v : adj57[u]) {
if (v == pr)continue;
if (vis[v]) {
if (vis[v] < vis[u])bck[u].push_back(v);
continue;
}
init(v, u);
tr[u].push_back(v);
}
}
void soly(int u, vector<int> vvo) {
if (vvo.empty())return;
vector<int> ee(n, n);
for (int j = 0; j < sz(vvo); j++) {
for (int i = 0; i < n; i++) {
if (findp(i) == vvo[j])ee[i] = -1;
}
}
ee[u] = -1;
if (sz(vvo) > 1) {
if (!chk(ee))return;
}
int l = 0, r = int(vvo.size()) - 1 - (sz(vvo) > 1), id = (sz(vvo) > 1 ? int(vvo.size())-1 : -1);
while (l <= r) {
int m = (l + r) >> 1;
vector<int> e(n, n);
for (int j = 0; j <= m; j++) {
for (int i = 0; i < n; i++) {
if (findp(i) == vvo[j])e[i] = -1;
}
}
e[u] = -1;
if (chk(e)) {
id = m;
r = m-1;
} else {
l = m+1;
}
}
if (~id) {
merge(u, vvo[id]);
} else {
return;
}
vector<int> xx;
for (int i = id+1; i < sz(vvo); i++) {
xx.push_back(vvo[i]);
}
soly(u, xx);
}
void dfs(int u) {
vector<int> vvo;
for (auto &v : bck[u]) {
if (findp(v) != findp(u))vvo.push_back(findp(v));
}
sort(vvo.begin(), vvo.end());
vvo.erase(unique(vvo.begin(), vvo.end()), vvo.end());
soly(u, vvo);
for (auto &v : tr[u]) {
if (chk2(u, v)) {
merge(u, v);
}
dfs(v);
}
}
void init2(int u, int pr) {
vis[u] = 1;
for (auto &v : adj2[u]) {
if (vis[v])continue;
dep[v] = (dep[u] ^ 1);
init2(v, u);
}
}
vector<int> nw(vector<int> x, int u) {
vector<int> reti;
for (auto &i : x) {
if (i == u)continue;
reti.push_back(i);
}
return reti;
}
void doyi() {
for (int i = 0; i < n; i++) {
if (fnd[i])break;
fnd[i] = true;
vector<int> ee(n, n);
ee[i] = -1;
int x = adj57[i][0];
for (int col = 0; col < n; col) {
ee[x] = col;
if (chk(ee)) {
ret[i] = col;
}
}
}
}
std::vector<int> find_colours(int NH, std::vector<int> X, std::vector<int> Y) {
n = NH;
fo.clear();
so.clear();
ret = vector<int> (n, 0);
for (int i = 0; i < n; i++) {
p[i] = i;
sz[i] = 1;
adj2[i].clear();
adj57[i].clear();
fnd[i] = false;
nds[i].clear();
tr[i].clear();
bck[i].clear();
vis[i] = 0;
}
for (int i = 0; i < X.size(); i++) {
int u = X[i], v = Y[i];
adj57[u].push_back(v);
adj57[v].push_back(u);
}
mmo = X.size();
init(0, 0);
dfs(0);
bool ff = true;
for (int i = 0; i < n; i++) {
ret[i] = findp(i);
ff &= (findp(i) == findp(0));
}
if (ff) {
for (int i = 0; i < n; i++) {
vector<int> e(n, n);
e[0] = -1;
e[adj57[0][0]] = i;
if (chk(e)) {
for (int j = 0; j < n; j++) {
ret[j] = i;
}
break;
}
}
return ret;
}
for (int i = 0; i < n; i++) {
nds[findp(i)].push_back(i);
for (auto &v : adj57[i]) {
if (findp(i) == findp(v))continue;
adj2[findp(i)].push_back(findp(v));
adj2[findp(v)].push_back(findp(i));
}
vis[i] = 0;
dep[i] = 0;
}
init2(findp(0), -1);
fo.clear();
so.clear();
for (int i = 0; i < n; i++) {
if (findp(i) != i)continue;
if (dep[i])fo.push_back(i);
else so.push_back(i);
}
doyi();
swap(fo, so);
for (int i = 0; i < n; i++) {
dep[i] ^= 1;
}
doyi();
return ret;
}
Compilation message
sphinx.cpp: In function 'void doyi()':
sphinx.cpp:172:36: warning: for increment expression has no effect [-Wunused-value]
172 | for (int col = 0; col < n; col) {
| ^~~
sphinx.cpp: In function 'std::vector<int> find_colours(int, std::vector<int>, std::vector<int>)':
sphinx.cpp:197:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for (int i = 0; i < X.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
584 KB |
#experiments reached 2751 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
#experiments: 2 |
| 2 |
Incorrect |
19 ms |
336 KB |
#experiments reached 2751 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
584 KB |
#experiments reached 2751 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
#experiments: 2 |
| 2 |
Incorrect |
19 ms |
336 KB |
#experiments reached 2751 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
#experiments: 2 |
| 2 |
Incorrect |
19 ms |
336 KB |
#experiments reached 2751 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
584 KB |
#experiments reached 2751 |
| 2 |
Halted |
0 ms |
0 KB |
- |
