#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
private:
vector<int> p;
public:
DisjointSet() {}
DisjointSet(int n) {
p.assign(n, 0);
iota(begin(p), end(p), 0);
}
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]);
}
bool Unite(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) return false;
p[x] = y;
return true;
}
bool SameSet(int x, int y) {
return Find(x) == Find(y);
}
};
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size();
vector<int> is_royal(m, -1); // undetermined: -1, not royal: 0, royal: 1
vector<vector<int>> adj(n);
DisjointSet dsu(n);
vector<int> T; // Spanning Tree of G
vector<vector<int>> Tadj(n);
vector<int> Tpar(n, -1);
vector<int> Tdepth(n, 0);
vector<bool> inT(n, false);
for (int i = 0; i < m; i++) {
adj[u[i]].emplace_back(i);
adj[v[i]].emplace_back(i);
if (dsu.Unite(u[i], v[i])) {
inT[i] = true;
T.emplace_back(i);
Tadj[u[i]].emplace_back(i);
Tadj[v[i]].emplace_back(i);
}
}
int Troyal = count_common_roads(T);
function<void(int, int)> dfs = [&](int cur, int p) {
for (auto e : Tadj[cur]) if (u[e] != p && v[e] != p) {
int nxt = u[e] == cur ? v[e] : u[e];
Tpar[nxt] = e;
Tdepth[nxt] = Tdepth[cur] + 1;
dfs(nxt, cur);
}
};
dfs(0, -1);
dsu = DisjointSet(n); // determine whether edges from u[i] and v[i] are all determined
function<void(int)> determine = [&](int edge) {
function<int(vector<int> T, int, int)> Query =
[&](vector<int> T, int remove, int add) {
T.erase(find(begin(T), end(T), remove));
T.emplace_back(add);
return count_common_roads(T);
};
vector<int> C; // Cycle
int a = u[edge], b = v[edge];
// Get edges of T in the cycle
if (Tdepth[a] > Tdepth[b]) swap(a, b);
while (Tdepth[b] > Tdepth[a]) {
C.emplace_back(Tpar[b]);
b = u[Tpar[b]] == b ? v[Tpar[b]] : u[Tpar[b]];
}
while (a != b) {
C.emplace_back(Tpar[a]);
C.emplace_back(Tpar[b]);
a = u[Tpar[a]] == a ? v[Tpar[a]] : u[Tpar[a]];
b = u[Tpar[b]] == b ? v[Tpar[b]] : u[Tpar[b]];
}
// check if there is an already determined edge
for (auto e : C) {
if (is_royal[edge] == -1 && is_royal[e] != -1) { // there is an already determined edge
int Nroyal = Query(T, e, edge);
if (Nroyal == Troyal) {
is_royal[edge] = is_royal[e];
} else {
is_royal[edge] = is_royal[e] ? 0 : 1;
}
}
}
// all edges are undetermined, check each of them
if (is_royal[edge] == -1) {
vector<int> same;
for (auto e : C) {
int Nroyal = Query(T, e, edge);
if (Nroyal == Troyal) {
same.emplace_back(e);
} else if (Nroyal < Troyal) { // e is a royal road while edge isn't
is_royal[e] = 1;
is_royal[edge] = 0;
break;
} else if (Nroyal > Troyal) { // e isn't a royal road while edge is
is_royal[e] = 0;
is_royal[edge] = 1;
break;
}
}
if (is_royal[edge] == -1) { // royal roads will never form a cycle
is_royal[edge] = 0;
}
// update edges which have the same royality as edge
for (auto e : same) {
is_royal[e] = is_royal[edge];
}
}
// we have determined edge, now to determine other edges in the cycle
for (auto e : C) {
if (is_royal[e] == -1) {
int Nroyal = Query(T, e, edge);
if (Nroyal == Troyal) {
is_royal[e] = is_royal[edge];
} else {
is_royal[e] = is_royal[edge] ? 0 : 1;
}
}
}
for (auto e : C) dsu.Unite(u[e], v[e]);
};
for (int i = 0; i < m; i++) {
if (inT[i]) continue; // edge is in T
if (dsu.SameSet(u[i], v[i])) continue; // all edges from u to v is already determined
determine(i); // determine royalities of cycle from u[i] to v[i]
}
for (auto e : T) {
if (is_royal[e] == -1) { // if it is not yet determined, that means e is a bridge
is_royal[e] = 1;
}
}
function<void(int)> find_royal = [&](int vertex) {
function<int(vector<int> T, vector<int> E)> Query =
[&](vector<int> T, vector<int> E) { // complete the golden set E with edges from T
DisjointSet d(n);
for (auto e : E) {
d.Unite(u[e], v[e]);
}
int royals_from_T = 0;
for (auto e : T) {
if (d.Unite(u[e], v[e])) {
royals_from_T += is_royal[e];
E.emplace_back(e);
}
}
return count_common_roads(E) - royals_from_T;
};
vector<int> adjacent;
for (auto e : adj[vertex]) {
if (u[e] == vertex) {
adjacent.emplace_back(e);
}
}
int count_royals = Query(T, adjacent);
for (int L = 0; count_royals > 0; count_royals--) {
int lo = L;
int hi = (int) adjacent.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
vector<int> E(begin(adjacent) + L, begin(adjacent) + mid + 1);
if (Query(T, E) > 0) {
hi = mid;
} else {
lo = mid + 1;
}
}
is_royal[adjacent[lo]] = 1;
for (int i = L; i < lo; i++) {
is_royal[adjacent[i]] = 0;
}
L = lo + 1;
}
};
// we have determined all roads in T, determine the remaining royal roads with binary search
for (int i = 0; i < n; i++) {
find_royal(i);
}
vector<int> royal_roads;
for (int i = 0; i < m; i++) {
if (is_royal[i]) {
royal_roads.emplace_back(i);
}
}
return royal_roads;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
correct |
| 2 |
Incorrect |
5 ms |
384 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
