#include "simurgh.h"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
class UnionFind {
int n;
vector<int> par, wei; // a[x] = a[r] + wei[x]
public:
UnionFind(int n_) : n(n_), par(n_, -1), wei(n, 0) {}
int find(int x) {
if (par[x] < 0) return x;
int r = find(par[x]);
wei[x] += wei[par[x]];
return par[x] = r;
}
int weight(int x) {
find(x);
return wei[x];
}
// a[x] = a[y] + w
bool merge(int x, int y, int w) {
w = weight(x) - w - weight(y);
x = find(x), y = find(y);
if (x == y) return false;
if (par[x] > par[y]) swap(x, y), w = -w;
par[x] += par[y];
par[y] = x;
wei[y] = w;
return true;
}
int diff(int x, int y) { return weight(y) - weight(x); }
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return -par[find(x)]; }
};
struct edge {
int to, idx;
bool operator==(const edge& e) const { return to == e.to && idx == e.idx; }
};
class BiConnectedComponents {
vector<vector<edge>> g;
vector<int> ord, low;
vector<int> stk;
vector<vector<int>> bcc;
int idx;
void dfs(int v, int p) {
ord[v] = low[v] = idx++;
for (auto e : g[v]) {
if (e.to == p) continue;
if (ord[e.to] == -1) {
stk.push_back(e.idx);
dfs(e.to, v);
chmin(low[v], low[e.to]);
if (ord[v] <= low[e.to]) {
vector<int> comp;
while (true) {
int f = stk.back();
stk.pop_back();
comp.push_back(f);
if (f == e.idx) break;
}
bcc.push_back(comp);
}
} else {
chmin(low[v], ord[e.to]);
if (ord[v] > ord[e.to]) stk.push_back(e.idx);
}
}
}
public:
BiConnectedComponents(int n) : g(n), ord(n, -1), low(n), idx(0) {}
void add_edge(int u, int v) {
g[u].push_back({v, idx});
g[v].push_back({u, idx});
++idx;
}
vector<vector<int>> build() {
idx = 0;
rep (i, g.size()) if (ord[i] == -1) dfs(i, -1);
return bcc;
}
};
map<vector<int>, int> memo;
int Query(vector<int> es) {
sort(all(es));
if (memo.count(es)) return memo[es];
return memo[es] = count_common_roads(es);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
if (n == 2) return {0};
BiConnectedComponents bcc(n);
rep (i, u.size()) bcc.add_edge(u[i], v[i]);
auto comp = bcc.build();
vector<int> cmpid(u.size(), -1);
rep (i, comp.size()) for (auto e : comp[i]) cmpid[e] = i;
vector<vector<edge>> g1(n);
rep (i, u.size()) {
g1[u[i]].push_back({v[i], i});
g1[v[i]].push_back({u[i], i});
}
vector<int> ans;
rep (c, comp.size()) {
if (comp[c].size() == 1) {
ans.push_back(comp[c][0]);
continue;
}
vector<int> es;
{
vector<bool> seen(n, false);
rep (i, n) {
auto dfs = [&](auto&& self, int v) -> void {
seen[v] = true;
for (auto e : g1[v]) if (!seen[e.to] && cmpid[e.idx] != c) {
es.push_back(e.idx);
self(self, e.to);
}
};
if (!seen[i]) {
dfs(dfs, i);
}
}
}
vector<int> U, V;
int n2 = 0;
{
vector<int> a;
for (auto i : comp[c]) {
a.push_back(u[i]);
a.push_back(v[i]);
}
sort(all(a));
a.erase(unique(all(a)), end(a));
for (auto i : comp[c]) {
U.push_back(lower_bound(all(a), u[i]) - begin(a));
V.push_back(lower_bound(all(a), v[i]) - begin(a));
}
n2 = a.size();
}
vector<vector<edge>> g(n2);
rep (i, U.size()) {
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
}
vector<int> es2;
vector<int> dep(n2, -1), par(n2, -1), pe(n2, -1);
{
auto dfs = [&](auto&& self, int v, int p) -> void {
for (auto e : g[v]) if (dep[e.to] == -1) {
es2.push_back(e.idx);
dep[e.to] = dep[v] + 1;
par[e.to] = v;
pe[e.to] = e.idx;
self(self, e.to, v);
}
};
dep[0] = 0;
dfs(dfs, 0, -1);
}
auto lca = [&](int u, int v) -> int {
while (u != v) {
if (dep[u] < dep[v]) swap(u, v);
u = par[u];
}
return u;
};
UnionFind uf(comp[c].size());
auto es_ = es;
for (auto i : es2) es.push_back(comp[c][i]);
int c1 = Query(es);
vector<bool> seen(comp[c].size(), false);
rep (i, comp[c].size()) {
if (count(all(es2), i)) continue;
int l = lca(U[i], V[i]);
if (dep[U[i]] < dep[V[i]]) swap(U[i], V[i]);
int v = U[i];
bool f = false;
while (v != l) {
if (!seen[pe[v]]) {
seen[pe[v]] = true;
f = true;
}
v = par[v];
}
if (!f) continue;
v = U[i];
while (v != l) {
int j = i, k = pe[v];
if (!uf.same(j, k)) {
auto es2 = es;
es2.erase(find(all(es2), comp[c][k]));
es2.push_back(comp[c][j]);
int c2 = Query(es2);
uf.merge(j, k, c2 - c1);
}
v = par[v];
}
}
int mn = 0;
int r = pe[1];
rep (i, comp[c].size()) if (uf.same(r, i)) chmin(mn, uf.weight(i));
vector<bool> is_common(comp[c].size(), false);
vector<int> used_es;
rep (i, comp[c].size()) if (uf.same(r, i)) {
if (uf.weight(i) != mn) {
ans.push_back(comp[c][i]);
is_common[i] = true;
}
g[U[i]].erase(find(all(g[U[i]]), edge{V[i], i}));
g[V[i]].erase(find(all(g[V[i]]), edge{U[i], i}));
used_es.push_back(i);
}
auto ask = [&](vector<int> es) {
UnionFind uf(n2);
for (auto i : es) uf.merge(U[i], V[i], 0);
int cnt = 0;
for (int i : used_es) {
if (uf.merge(U[i], V[i], 0)) {
es.push_back(i);
if (is_common[i]) ++cnt;
}
}
for (auto& i : es) i = comp[c][i];
for (auto i : es_) es.push_back(i);
return Query(es) - cnt;
};
int c2 = ask({});
rep (i, n2) {
vector<int> es;
for (auto e : g[i]) es.push_back(e.idx);
int t = ask(es) - c2;
rep (i, t) {
int ok = 0, ng = es.size();
while (ok - ng > 1) {
int mid = (ok + ng) / 2;
vector<int> es2;
rep (j, mid) es2.push_back(es[j]);
if (ask(es2) - c2 > i) ng = mid;
else ok = mid;
}
ans.push_back(comp[c][es[ok]]);
}
for (auto e : g[i]) {
g[e.to].erase(find(all(g[e.to]), edge{i, e.idx}));
}
}
}
sort(all(ans));
ans.erase(unique(all(ans)), ans.end());
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
