#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
vector<int> par;
void init(int sz) {
par.resize(sz, -1);
}
int root(int pos) {
if (par[pos] == -1) return pos;
par[pos] = root(par[pos]);
return par[pos];
}
void unite(int u, int v) {
u = root(u); v = root(v); if (u == v) return;
par[u] = v;
}
bool same(int u, int v) {
if (root(u) == root(v)) return true;
return false;
}
};
int N, M, A[1 << 18], B[1 << 18], id[509][509]; vector<pair<int, int>> X[509];
vector<int> ans, G[509], F; bool used[509], forced[509];
vector<int> anti_spanning_tree(int pos) {
vector<int>E; UnionFind UF; UF.init(N);
for (int i = 0; i < M; i++) {
if (A[i] == pos || B[i] == pos) continue;
if (UF.same(A[i], B[i]) == false) {
E.push_back(i);
UF.unite(A[i], B[i]);
}
}
return E;
}
void hantei(vector<int> vec, vector<int> r) {
vector<int> L; int maxn = 0;
for (int pos : r) {
vector<int> vec2 = vec; vec2.push_back(pos);
assert(vec2.size() == N - 1);
int E = count_common_roads(vec2);
maxn = max(maxn, E); L.push_back(E);
}
for (int j = 0; j < r.size(); j++) {
if (L[j] == maxn) ans.push_back(r[j]);
}
}
void dfs(int pos) {
if (used[pos] == true) return;
used[pos] = true; if (forced[pos] == true) F.push_back(pos);
for (int i = 0; i < G[pos].size(); i++) {
dfs(G[pos][i]);
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
N = n; M = u.size();
for (int i = 0; i < M; i++) {
A[i] = u[i]; B[i] = v[i];
X[A[i]].push_back(make_pair(B[i], i));
X[B[i]].push_back(make_pair(A[i], i));
id[A[i]][B[i]] = i;
id[B[i]][A[i]] = i;
}
for (int i = 0; i < N; i++) {
vector<int> vec = anti_spanning_tree(i);
for (int j = 0; j < N; j++) { used[j] = false; forced[j] = false; G[j].clear(); }
for (int pos : vec) {
G[A[pos]].push_back(B[pos]);
G[B[pos]].push_back(A[pos]);
}
for (pair<int, int> pos : X[i]) forced[pos.first] = true;
vector<vector<int>> U;
for (int j = 0; j < N; j++) {
if (j == i || used[j] == true) continue;
F.clear(); dfs(j);
vector<int>FF; for (int pos : F) FF.push_back(id[i][pos]);
F = FF; U.push_back(F);
}
for (int j = 0; j < U.size(); j++) {
vector<int> F = U[j];
vector<int> vec3 = vec;
for (int k = 0; k < U.size(); k++) {
if (j == k) continue;
vec3.push_back(id[i][U[k][0]]);
}
hantei(vec3, F);
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
assert(ans.size() != N - 1);
//for (int i = 0; i < ans.size(); i++) cout << ans[i] << ", "; cout << endl;
return ans;
}
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:2:
simurgh.cpp: In function 'void hantei(std::vector<int>, std::vector<int>)':
simurgh.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(vec2.size() == N - 1);
~~~~~~~~~~~~^~~~~~~~
simurgh.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < r.size(); j++) {
~~^~~~~~~~~~
simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < U.size(); j++) {
~~^~~~~~~~~~
simurgh.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < U.size(); k++) {
~~^~~~~~~~~~
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:2:
simurgh.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(ans.size() != N - 1);
~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 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 |
Runtime error |
2 ms |
512 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 |
Runtime error |
2 ms |
512 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 |
Runtime error |
2 ms |
512 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 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
