#include <bits/stdc++.h>
using namespace std;
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
int count_common_roads(vector<int> r) {
return 1;
}
vector <int> find_roads(int n, vector<int> fe, vector<int> se) {
int m = fe.size();
vector<vector<int>> g(n);
vector<int> to(2 * m);
for (int i = 0; i < m; i++) {
int u = fe[i], v = se[i];
to[i << 1] = v;
to[(i << 1) + 1] = u;
g[u].push_back(i << 1);
g[v].push_back((i << 1) + 1);
}
vector<int> ret(m, -1);
auto calc = [&](int p, vector<int> adj) {
dsu d(n);
vector<int> edges;
for (int i = 0; i < m; i++) {
int u = to[i * 2], v = to[i * 2 + 1];
if (u == p || v == p) {
continue;
}
d.unite(u, v);
edges.push_back(i);
}
sort(adj.begin(), adj.end(), [&](int i, int j){ return d.get(to[i]) < d.get(to[j]); });
int sz = adj.size();
for (int i = 0; i < sz; i++) {
if (i == 0 || d.get(to[adj[i]]) != d.get(to[adj[i - 1]])) {
edges.push_back(i >> 1);
}
}
assert((int) edges.size() == n - 1);
int sum = count_common_roads(edges);
vector<int> val(sz, 1);
int beg = 0, fin = 0;
while (beg < sz) {
while (fin + 1 < sz && d.get(to[adj[fin + 1]]) == d.get(to[adj[beg]])) {
fin += 1;
}
vector<int> cur = edges;
cur.erase(find(cur.begin(), cur.end(), adj[beg] >> 1));
for (int i = beg + 1; i <= fin; i++) {
cur.push_back(adj[i] >> 1);
val[i] = val[beg] + count_common_roads(cur) - sum;
cur.pop_back();
}
if (*max_element(val.begin() + beg, val.begin() + fin + 1) > 1) {
for (int i = beg; i <= fin; i++) {
val[i] -= 1;
}
}
beg = fin + 1;
}
for (int i = 0; i < sz; i++) {
assert(0 <= val[i] && val[i] <= 1);
ret[adj[i] >> 1] = val[i];
}
};
vector<int> que;
vector<int> par(n, m);
que.push_back(0);
par[0] = -1;
for (int b = 0; b < (int) que.size(); b++) {
int p = que[b];
vector<int> add;
for (int e : g[p]) {
if (par[to[e]] == m) {
add.push_back(e);
que.push_back(to[e]);
par[to[e]] = e;
}
}
if (par[p] != -1) {
add.push_back(par[p]);
}
calc(p, add);
}
vector<int> tree;
for (int i = 0; i < m; i++) {
if (ret[i] != -1) {
tree.push_back(i);
}
}
assert(tree.size() == n - 1);
auto solve = [&](vector<int> edge) {
dsu d(n);
for (int i : edge) {
int u = to[2 * i], v = to[2 * i + 1];
assert(d.unite(u, v));
}
int sum = 0;
for (int i : tree) {
int u = to[2 * i], v = to[2 * i + 1];
if (d.unite(u, v)) {
sum -= ret[i];
edge.push_back(i);
}
}
assert(edge.size() == n - 1);
return sum + count_common_roads(edge);
};
for (int i = 0; i < n; i++) {
vector<int> gr;
for (int j : g[i]) {
if (ret[j >> 1] == -1) {
gr.push_back(j >> 1);
}
}
int sz = gr.size();
function<void(int, int)> dfs = [&](int L, int R) {
int val = solve(vector<int>(gr.begin() + L, gr.begin() + R + 1));
for (int i = L; i <= R; i++) {
if (val == 0) {
ret[gr[i]] = 0;
} else if (L == R) {
ret[gr[i]] = 1;
}
}
if (L < R && val > 0) {
int M = (L + R) >> 1;
dfs(L, M);
dfs(M + 1, R);
}
};
dfs(0, sz - 1);
}
vector<int> ans;
for (int i = 0; i < m; i++) {
if (ret[i] == 1) {
ans.push_back(i);
}
}
return ans;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/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:123:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
123 | assert(tree.size() == n - 1);
| ~~~~~~~~~~~~^~~~~~~~
simurgh.cpp: In lambda function:
simurgh.cpp:139:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
139 | assert(edge.size() == n - 1);
| ~~~~~~~~~~~~^~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Runtime error |
1 ms |
436 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
