Submission #1035763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035763		ALeonidou	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	348 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

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){
	// dbg(u);
	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]){
			// dbg2(u,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)
vi span_tree(ll n, ll m, ll processed_node, vi &u, vi &v, vi &royal_edges, vi &royal_edges_grid, ll on_edge = -1){
	vi q;
	//init DSU:
	par.resize(n);
	for (ll j =0; j<n; j++){
		par[j] = j;
	}
	siz.assign(n, 1);
	//connect on edge:
	if (on_edge != -1){
		onion(u[on_edge], v[on_edge]);
		q.pb(on_edge);
	}
	//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]);
	}
	//rest of the edges without adding illegal edges
	for (ll j=0; j<m && sz(q) < n-1; j++){
		if (royal_edges_grid[j]) continue;
		ll a = v[j], b = u[j];
		if (a != processed_node && b != processed_node && fnd(a) != fnd(b)){
			onion(a,b);
			q.pb(j);
		}
	}
	// cout<<"q:";
	// printVct(q);
	//validate span tree:
	bool ok = true;
	for (ll j =1; j<n; j++){
		if (fnd(j) != fnd(j-1)){
			ok = false;
		}
	}
	if (!ok){
		q = vi();
	}
	return q;
}

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, processed_edgs(m, 0), royal_edges_grid(m, 0);
	for (ll i =0; i<m; i++){
		if (bridges[i]){
			processed_edgs[i] = 1;
			royal_edges.pb(i);
			royal_edges_grid[i] = 1;
		}
	}

	// cout<<"royal:";
	// printVct(royal_edges);


	//step 2:
	for (ll i =0; i<n; i++){	//process nodes one by one
		// dbg(i);
		vi edges_to_process, q;
		for (ll j =0; j<sz(adj[i]); j++){
			ll id = adj[i][j].S;
			if (!processed_edgs[id]){
				edges_to_process.pb(id);
				processed_edgs[id] = 1;
			}
		}
		if (sz(edges_to_process) == 0) continue;
		
		// cout<<"edges_to_process: ";
		// printVct(edges_to_process);
		// return vi();

		//create span tree: O(N + M)
		q = span_tree(n,m,i,u,v,royal_edges,royal_edges_grid);
		// printVct(q);

		bool empty_is_valid = !q.empty();

		//Turn processed edges on/off
		if (sz(edges_to_process) == 1){
			ll val = count_common_roads(q);
			q = span_tree(n,m,i,u,v,royal_edges,royal_edges_grid,edges_to_process[0]);
			if (q.empty()) continue;
			ll x = count_common_roads(q);
			if (x > val){
				royal_edges.pb(edges_to_process[0]);
				royal_edges_grid[edges_to_process[0]] = 1;
			}
		}
		else{
			vii res; 	//res, id
			for (ll j = 0; j<sz(edges_to_process); j++){
				q = span_tree(n,m,i,u,v,royal_edges,royal_edges_grid,edges_to_process[j]);
				if (q.empty()) continue;
				// printVct(q);
				ll x = count_common_roads(q);
				res.pb(ii(x,edges_to_process[j]));
			}

			ll mini = res[0].F, maxi = res[0].S;
			for (ll j =0; j<sz(res); j++){
				mini = min(res[j].F, mini);
				maxi = max(res[j].F, maxi);
			}

			if (mini == maxi){
				for (ll j =0; j<sz(res); j++){
					royal_edges.pb(res[j].S);
					royal_edges_grid[res[j].S] = 1;
				}	
			}
			else{
				for (ll j =0; j<sz(res); j++){
					if (res[j].F == maxi){
						royal_edges.pb(res[j].S);
						royal_edges_grid[res[j].S] = 1;
					}
				}
			}
		}
	}

	// cout<<endl<<"ans:";
	// printVct(royal_edges);
	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

*/

Compilation message (stderr)

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:160:8: warning: unused variable 'empty_is_valid' [-Wunused-variable]
  160 |   bool empty_is_valid = !q.empty();
      |        ^~~~~~~~~~~~~~

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