#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
using pii = pair<int, int>;
const int N = 510;
const int M = N*(N-1)/2;
const int LIM = 30000;
vector<pii> G[N];
vector<int> E;
int par[N];
int root(int u) {
if (par[u] == u) return u;
return par[u] = root(par[u]);
}
bool merge(int u, int v) {
u = root(u), v = root(v);
if (u == v) return false;
par[u] = v;
return true;
}
bool tree[M];
int ans[N];
vector<int> find_roads(int n, vector<int> U, vector<int> V)
{
int cntq = 0;
int m = U.size();
iota(par, par+n, 0);
fill(ans, ans+m, -1);
for (int i = 0; i < m; ++i) {
int u = U[i], v = V[i];
if (merge(u, v)) {
G[u].emplace_back(v, i);
G[v].emplace_back(u, i);
E.push_back(i);
tree[i] = true;
}
}
if (++cntq == LIM) assert(false);
int defcnt = count_common_roads(E);
for (int i = 0; i < m; ++i) if (!tree[i]) {
int u = U[i], v = V[i];
vector<int> par(n, -1);
vector<int> ix(n, -1);
par[u] = u;
queue<int> Q;
Q.push(u);
while (!Q.empty()) {
int s = Q.front(); Q.pop();
if (s == v) break;
for (auto t : G[s]) if (par[t.first] == -1) {
par[t.first] = s;
ix[t.first] = t.second;
Q.push(t.first);
}
}
map<int, bool> inp;
vector<int> path;
int s = v;
do {
inp[ix[s]] = true;
path.push_back(ix[s]);
s = par[s];
} while (s != u);
int typ = -1; // not -1 = found determined
for (auto e : path) {
if (ans[e] != -1) {
typ = e;
break;
}
}
vector<int> other;
for (auto e : E) {
if (!inp[e])
other.push_back(e);
}
if (typ == -1) {
ans[i] = 0;
for (auto e : path) {
vector<int> q(other.begin(), other.end());
for (auto p : path) if (p != e)
q.push_back(p);
q.push_back(i);
if (++cntq == LIM) assert(false);
int cnt = count_common_roads(q);
if (cnt-defcnt == 1)
ans[e] = 0, ans[i] = 1;
else if (cnt-defcnt == -1)
ans[i] = 0, ans[e] = 1;
}
if (ans[i] == -1) ans[i] = 0;
for (auto e : path) if (ans[e] == -1)
ans[e] = ans[i];
} else {
vector<int> q(other.begin(), other.end());
for (auto e : path) if (e != typ)
q.push_back(e);
q.push_back(i);
if (++cntq == LIM) assert(false);
int cnt = count_common_roads(q);
ans[i] = ans[typ]+(cnt-defcnt);
for (auto e : path) if (ans[e] == -1) {
q = vector<int>(other.begin(), other.end());
for (auto p : path) if (p != e) q.push_back(p);
q.push_back(i);
if (++cntq == LIM) assert(false);
int cnt = count_common_roads(q);
if (cnt-defcnt == 1) ans[e] = 0;
else if (cnt-defcnt == -1) ans[e] = 1;
else ans[e] = ans[i];
}
}
}
vector<int> ret;
ret.reserve(n-1);
for (int i = 0; i < m; ++i) {
if (ans[i] != 0)
ret.push_back(i);
}
assert(ret.size() == n-1);
iota(par, par+n, 0);
for (auto e : ret)
assert(merge(U[e], V[e]));
return ret;
}
Compilation message
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 simurgh.cpp:1:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:126:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(ret.size() == n-1);
~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
correct |
| 2 |
Correct |
2 ms |
360 KB |
correct |
| 3 |
Correct |
3 ms |
568 KB |
correct |
| 4 |
Correct |
2 ms |
568 KB |
correct |
| 5 |
Correct |
2 ms |
568 KB |
correct |
| 6 |
Correct |
2 ms |
568 KB |
correct |
| 7 |
Correct |
2 ms |
600 KB |
correct |
| 8 |
Correct |
2 ms |
604 KB |
correct |
| 9 |
Correct |
2 ms |
612 KB |
correct |
| 10 |
Correct |
2 ms |
612 KB |
correct |
| 11 |
Correct |
3 ms |
616 KB |
correct |
| 12 |
Correct |
3 ms |
664 KB |
correct |
| 13 |
Correct |
2 ms |
668 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
correct |
| 2 |
Correct |
2 ms |
360 KB |
correct |
| 3 |
Correct |
3 ms |
568 KB |
correct |
| 4 |
Correct |
2 ms |
568 KB |
correct |
| 5 |
Correct |
2 ms |
568 KB |
correct |
| 6 |
Correct |
2 ms |
568 KB |
correct |
| 7 |
Correct |
2 ms |
600 KB |
correct |
| 8 |
Correct |
2 ms |
604 KB |
correct |
| 9 |
Correct |
2 ms |
612 KB |
correct |
| 10 |
Correct |
2 ms |
612 KB |
correct |
| 11 |
Correct |
3 ms |
616 KB |
correct |
| 12 |
Correct |
3 ms |
664 KB |
correct |
| 13 |
Correct |
2 ms |
668 KB |
correct |
| 14 |
Runtime error |
3 ms |
928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
correct |
| 2 |
Correct |
2 ms |
360 KB |
correct |
| 3 |
Correct |
3 ms |
568 KB |
correct |
| 4 |
Correct |
2 ms |
568 KB |
correct |
| 5 |
Correct |
2 ms |
568 KB |
correct |
| 6 |
Correct |
2 ms |
568 KB |
correct |
| 7 |
Correct |
2 ms |
600 KB |
correct |
| 8 |
Correct |
2 ms |
604 KB |
correct |
| 9 |
Correct |
2 ms |
612 KB |
correct |
| 10 |
Correct |
2 ms |
612 KB |
correct |
| 11 |
Correct |
3 ms |
616 KB |
correct |
| 12 |
Correct |
3 ms |
664 KB |
correct |
| 13 |
Correct |
2 ms |
668 KB |
correct |
| 14 |
Runtime error |
3 ms |
928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
928 KB |
correct |
| 2 |
Correct |
4 ms |
928 KB |
correct |
| 3 |
Runtime error |
25 ms |
4136 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 |
3 ms |
248 KB |
correct |
| 2 |
Correct |
2 ms |
360 KB |
correct |
| 3 |
Correct |
3 ms |
568 KB |
correct |
| 4 |
Correct |
2 ms |
568 KB |
correct |
| 5 |
Correct |
2 ms |
568 KB |
correct |
| 6 |
Correct |
2 ms |
568 KB |
correct |
| 7 |
Correct |
2 ms |
600 KB |
correct |
| 8 |
Correct |
2 ms |
604 KB |
correct |
| 9 |
Correct |
2 ms |
612 KB |
correct |
| 10 |
Correct |
2 ms |
612 KB |
correct |
| 11 |
Correct |
3 ms |
616 KB |
correct |
| 12 |
Correct |
3 ms |
664 KB |
correct |
| 13 |
Correct |
2 ms |
668 KB |
correct |
| 14 |
Runtime error |
3 ms |
928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
