#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl "\n"
#define sz(x) (ll)x.size()
#define F first
#define S second
#define pb push_back
#define ins insert
#define INF 10000000
typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
void printVct(vi &v){
for (ll i =0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
vector < vii > adj;
vi dp, h, vis;
vi bridges;
void dfs(ll u, ll height, ll p){
h[u] = height;
dp[u] = height;
vis[u] = 1;
for (ll i =0; i<sz(adj[u]); i++){
ll c = adj[u][i].F;
if (c == p) continue;
if (!vis[c]){
dfs(c, height+1, u);
}
dp[u] = min(dp[u], dp[c]);
if (dp[u] == dp[c]){
bridges[adj[u][i].S] = 0;
}
}
}
vi par, siz;
ll fnd(ll x){
if (x == par[x]) return x;
return par[x] = fnd(par[x]);
}
void onion(ll a, ll b){
a = fnd(a);
b = fnd(b);
if (a != b){
if (siz[a] < siz[b]) swap(a,b);
par[b] = a;
siz[a] += siz[b];
}
}
//create span tree: O(N + M)
void span_tree(vi &q, vi ¬_q, vector <vii> &cadj, ll n, ll m, vi &u, vi &v, vi &royal_edges, vi &royal_edges_grid, vi &removed_edges_grid){
cadj.assign(n, vii());
//init DSU:
par.resize(n);
for (ll j =0; j<n; j++){
par[j] = j;
}
siz.assign(n, 1);
//connect royal edges:
for (ll j =0; j<sz(royal_edges); j++){
ll a = v[royal_edges[j]], b = u[royal_edges[j]];
onion(a, b);
q.pb(royal_edges[j]);
cadj[a].pb(ii(b,j));
cadj[b].pb(ii(a,j));
}
//rest of the edges without adding illegal edges
ll lastPos = 0;
for (ll j=0; j<m && sz(q) < n-1; j++){
if (royal_edges_grid[j] || removed_edges_grid[j]) continue;
ll a = v[j], b = u[j];
if (fnd(a) != fnd(b)){
onion(a,b);
q.pb(j);
cadj[a].pb(ii(b,j));
cadj[b].pb(ii(a,j));
}
else{
not_q.pb(j);
}
lastPos = j+1;
}
for (ll j = lastPos; j<m; j++){
not_q.pb(j);
}
}
bool dfs2(ll u, vector <vii> &cadj, vi &cycle_edges){
vis[u] = 1;
for (ll i = 0; i<sz(cadj[u]); i++){
if (!vis[cadj[u][i].F]){
if (dfs2(cadj[u][i].F, cadj, cycle_edges)){
cycle_edges.pb(cadj[u][i].S);
return true;
}
}
else{
cycle_edges.pb(cadj[u][i].S);
}
}
return false;
}
vi find_roads(int n, vi u, vi v) {
ll m = sz(u);
adj.assign(n, vii());
for (ll i =0; i<m; i++){
adj[u[i]].pb(ii(v[i], i));
adj[v[i]].pb(ii(u[i], i));
}
// step 1: find all bridges and mark them as royal
bridges.assign(m, 1);
h.resize(n);
vis.assign(n, 0);
dp.resize(n);
dfs(0,0,-1);
vi royal_edges, removed_edges_grid(m, 0), royal_edges_grid(m, 0);
for (ll i =0; i<m; i++){
if (bridges[i]){
royal_edges.pb(i);
royal_edges_grid[i] = 1;
}
}
while (sz(removed_edges_grid) < n-1){
vi q, not_q;
vector <vii> cadj;
span_tree(q,not_q,cadj,n,m,u,v,royal_edges,royal_edges_grid,removed_edges_grid);
for (ll i = 0; i<sz(not_q); i++){
ll back_edge = not_q[i];
cadj[u[back_edge]].pb(ii(v[back_edge], back_edge));
cadj[v[back_edge]].pb(ii(u[back_edge], back_edge));
vi cycle_edges;
dfs2(u[back_edge],cadj,cycle_edges);
//check which cycle edges are not processed
vi tmp;
for (ll j =0; j<sz(cycle_edges); j++){
if (!royal_edges_grid[cycle_edges[j]]){
tmp.pb(cycle_edges[j]);
}
}
cycle_edges = tmp;
if (sz(cycle_edges) == 0) continue;
if (sz(cycle_edges) == 1){
removed_edges_grid[cycle_edges[0]] = 1;
break;
}
set <ll> cycle_edges_set;
for (ll j =0; j<sz(cycle_edges); j++){
cycle_edges_set.ins(cycle_edges[j]);
}
tmp.clear();
for (ll j = 0; j<sz(q); j++){
if (cycle_edges_set.find(q[j]) == cycle_edges_set.end()){
tmp.pb(q[j]);
}
}
q = tmp;
ll mini = INF, maxi = -1;
vii res;
for (ll j = 0; j<sz(cycle_edges); j++){
for (ll k =0; k<sz(cycle_edges); k++){
if (k == j) continue;
q.pb(cycle_edges[k]);
}
ll x = count_common_roads(q);
mini = min(x, mini);
maxi = max(x, maxi);
res.pb(ii(x, cycle_edges[j]));
for (ll k =0; k<sz(cycle_edges); k++){
if (k == j) continue;
q.pop_back();
}
}
bool removed_any = false;
for (ll j = 0; j<sz(res); j++){
if (res[j].F == maxi){
removed_edges_grid[res[j].S] = 1;
removed_any = true;
}
else{
royal_edges_grid[res[j].S] = 1;
}
}
if (removed_any) break;
}
}
return royal_edges;
}
/*
5 7
0 1
0 2
0 3
1 2
1 3
2 3
3 4
0 1 5 6
5 5
0 1
1 2
1 3
2 3
3 4
0 1 2 4
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
436 KB |
correct |
| 2 |
Incorrect |
0 ms |
344 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
