Submission #1029146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029146		AmirAli_H1	Simurgh (IOI17_simurgh)	C++17	13 / 100	3095 ms	600 KiB

simurgh

// In the name of Allah
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 500 + 7;

int n, m;
vector<int> adj[maxn];
int mark[maxn], par[maxn];
int markx[maxn], M[maxn][maxn];
int ind[maxn][maxn], markw[maxn];
vector<int> res, ls, lsx, vc;

void dfs(int v) {
	markw[v] = 1;
	for (int u : adj[v]) {
		if (!markw[u]) {
			ls.pb(ind[v][u]);
			dfs(u);
		}
	}
}

bool okx(int v) {
	ls.clear();
	for (int i = 0; i < n; i++) markw[i] = mark[i];
	markw[v] = 1;
	dfs(0); int T = -len(ls);
	for (int u = 0; u < n; u++) {
		if (u == v) continue;
		if (mark[u]) ls.pb(ind[u][par[u]]);
		else T++;
	}
	return (T == 1);
}

void checkx(int v) {
	int t = 0, j = -1;
	for (int u = 0; u < n; u++) {
		if (mark[u]) continue;
		if (M[v][u]) {
			t++; j = u;
		}
	}
	if (t == 1) {
		par[v] = j;
		mark[v] = 1;
	}
}

void check(int v) {
	if (!markx[v] && okx(v)) {
		bool flag = 0;
		int mx = -1; vc.clear();
		for (int u : adj[v]) {
			if (mark[u] || (markx[u] && flag)) continue;
			lsx.clear(); lsx = ls;
			lsx.pb(ind[u][v]);
			int R = count_common_roads(lsx);
			if (R > mx) {
				mx = R;
				vc.clear(); vc.pb(u);
			}
			else if (R == mx) vc.pb(u);
			if (markx[u]) flag = 1;
		}
		for (int u : vc) M[v][u] = M[u][v] = 1;
		markx[v] = 1;
	}
	if (markx[v]) checkx(v);
}

vector<int> find_roads(int Nx, vector<int> ux, vector<int> vx) {
	n = Nx; m = len(ux);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) ind[i][j] = -1;
	}
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adj[v].pb(u);
		ind[u][v] = ind[v][u] = i;
	}
	
	while (true) {
		int T = 0;
		for (int v = 1; v < n; v++) {
			if (!mark[v]) {
				check(v);
				T += 1;
			}
		}
		if (T == 0) break;
	}
	
	for (int v = 1; v < n; v++) {
		int u = par[v];
		res.pb(ind[u][v]);
	}
	return res;
}

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