#include "simurgh.h"
#include<utility>
#include<queue>
#include<algorithm>
#define x first
#define y second
#define pi pair<int,int>
using namespace std;
vector<vector<pi>>l;
vector<int>mm;
int vs[505], p[505], pl[505], up[505], cs[505], T = 1;
void dfs(int n, int p) {
::p[n] = p;
vs[n] = T++;
for (pi e : l[n]) {
if (e.x == p) {
pl[n] = e.y;
}
if (vs[e.x] == 0)dfs(e.x, n);
}
}
int f(int n) {
if (n == up[n])return n;
return up[n] = f(up[n]);
}
void un(int a, int b) {
a = f(a);
b = f(b);
up[a] = b;
}
vector<int> find_roads(int n, vector<int>u, vector<int>v) {
int i, j, r, m = v.size(), k, nn, ln;
vector<int>qv;
mm.resize(m, -1);
l.resize(n);
while (m--) {
l[u[m]].push_back({ v[m],m });
l[v[m]].push_back({ u[m],m });
}
dfs(0, -1);
for (i = 1; i < n; i++)qv.push_back(pl[i]);
k = count_common_roads(qv);
for (i = 1; i < n; i++) {
nn = ln = p[i];
for (pi e : l[i]) {
if (vs[e.x] < vs[nn]) {
nn = e.x;
ln = e.y;
}
}
//printf("%d %d\n", i, p[i]);
if (nn == p[i])continue;
//printf("%d [%d]\n", i, nn);
int b = 0, c = 1;
for (j = i; j != nn; j = p[j]) {
r = pl[j];
if (mm[r] >= 0)continue;
c = 0;
qv.clear();
qv.push_back(ln);
for (int ii = 1; ii < n; ii++)if (pl[ii] != r)qv.push_back(pl[ii]);
mm[r] = 3 + count_common_roads(qv) - k;//3+that road-this road
if (mm[r] != 3)b = mm[r] - 3;
}
if (c)continue;
if (b == 1) {
//printf("Case 1\n");
for (j = i; j != nn; j = p[j]) {
r = pl[j];
if (mm[r] > 1) {
mm[r] = 4 - mm[r];
}
}
}
else if (b == -1) {
//printf("Case 2\n");
for (j = i; j != nn; j = p[j]) {
r = pl[j];
if (mm[r] > 1) {
mm[r] = 3 - mm[r];
}
}
}
else {
//printf("Case 3\n");
int K = -1;
for (j = i; j != nn; j = p[j]) {
r = pl[j];
if (mm[r] < 2) {
qv.clear();
qv.push_back(ln);
for (int ii = 1; ii < n; ii++)if (pl[ii] != r)qv.push_back(pl[ii]);
K = count_common_roads(qv) - k + mm[r];
break;
}
}
if (K < 0) {
for (j = i; j != nn; j = p[j]) {
r = pl[j];
mm[r] = 0;
}
}
else {
for (j = i; j != nn; j = p[j]) {
r = pl[i];
if (mm[r] < 2)continue;
mm[r] = K;
}
}
}
}
for (i = 1; i < n; i++) {
if (mm[pl[i]] < 0)mm[pl[i]] = 1;
}
queue<int>q;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)up[j] = j;
qv.clear();
for (pi e : l[i]) {
qv.push_back(e.y);
un(e.x, i);
}
k = 0;
for (j = 1; j < n; j++) {
if (f(j) != f(p[j])) {
un(j, p[j]);
qv.push_back(pl[j]);
k += mm[pl[j]];
}
}
cs[i] = count_common_roads(qv) - k;
if (cs[i] == 1)q.push(i);
}
//for (i = 0; i < n; i++)printf("%d ", cs[i]);
//printf("\n");
//m = u.size();
//for (i = 0; i < m; i++)printf("%d ", mm[i]);
//printf("\n");
vector<pi>vv;
while (q.size()) {
i = q.front();
q.pop();
//printf("Test: %d\n", i);
if (cs[i] != 1)continue;
//printf("Yeah\n");
vv.clear();
for (pi e : l[i]) {
if (cs[e.x])vv.push_back(e);
}
while (vv.size() > 1) {
//printf("[ ");
//for (pi e : vv)printf("%d ", e.y);
//printf("]\n");
for (j = 0; j < n; j++)up[j] = j;
qv.clear();
for (j = 0; j < vv.size() / 2; j++) {
qv.push_back(vv[j].y);
un(vv[j].x, i);
}
k = 0;
for (j = 1; j < n; j++) {
if (f(j) != f(p[j])) {
un(j, p[j]);
qv.push_back(pl[j]);
k += mm[pl[j]];
}
}
//printf("%d %d\n", k, count_common_roads(qv));
if (count_common_roads(qv) == k) {
vv.erase(vv.begin(), vv.begin() + (vv.size() / 2));
}
else {
vv.erase(vv.begin() + (vv.size() / 2), vv.end());
}
}
//printf("[ ");
//for (pi e : vv)printf("%d ", e.y);
//printf("]\n");
for (pi e : l[i]) {
if (e.x == vv[0].x) {
mm[e.y] = 1;
cs[e.x]--;
if (cs[e.x] == 1)q.push(e.x);
}
else if (mm[e.y] == -1) {
mm[e.y] = 0;
}
}
cs[i] = 0;
}
m = u.size();
//for (i = 0; i < m; i++)printf("%d ", mm[i]);
//printf("\n");
vector<int>ans;
for (i = 0; i < m; i++) {
if (mm[i] == 1)ans.push_back(i);
}
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:156:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for (j = 0; j < vv.size() / 2; j++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
280 KB |
correct |
| 2 |
Incorrect |
0 ms |
292 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
280 KB |
correct |
| 2 |
Incorrect |
0 ms |
292 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
280 KB |
correct |
| 2 |
Incorrect |
0 ms |
292 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
288 KB |
correct |
| 2 |
Incorrect |
0 ms |
204 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
280 KB |
correct |
| 2 |
Incorrect |
0 ms |
292 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
