Submission #1036750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036750		ALeonidou	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	436 KiB

simurgh

#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 &not_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

*/

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30