Submission #431626

#	Time	Username	Problem	Language	Result	Execution time	Memory
431626		rainboy	Simurgh (IOI17_simurgh)	C++98	51 / 100	210 ms	3404 KiB

simurgh

#include "simurgh.h"
#include <string.h>

using namespace std;

#define N	240
#define M	(N * (N - 1) / 2)

typedef vector<int> vi;

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

char cc[M]; int qu[M], cnt;

vi find_roads(int n, vi ii, vi jj) {
	int m = ii.size(), m_, g, h, h_, k, k_;
	vi hh(n - 1);

	memset(cc, -1, m * sizeof *cc);
	while (1) {
		memset(ds, -1, n * sizeof *ds);
		m_ = 0;
		for (h = 0; h < m; h++)
			if (cc[h] == 1)
				join(ii[h], jj[h]), hh[m_++] = h;
		if (m_ == n - 1)
			break;
		g = m_;
		for (h = 0; h < m; h++)
			if (cc[h] == -1 && join(ii[h], jj[h]))
				hh[m_++] = h;
		k = count_common_roads(hh);
		memset(ds, -1, n * sizeof *ds);
		for (h = 0; h < n - 1; h++)
			if (h != g)
				join(ii[hh[h]], jj[hh[h]]);
		h_ = hh[g];
		cnt = 0, qu[cnt++] = h_;
		for (h = 0; h < m; h++)
			if (cc[h] == -1 && h != h_ && find(ii[h]) != find(jj[h])) {
				hh[g] = h;
				k_ = count_common_roads(hh);
				if (k_ == k + 1) {
					while (cnt--)
						cc[qu[cnt]] = 0;
					cc[h] = 1;
					break;
				} else if (k_ == k - 1) {
					while (cnt--)
						cc[qu[cnt]] = 1;
					cc[h] = 0;
					break;
				}
				qu[cnt++] = h;
			}
		if (cnt > 0)
			while (cnt--)
				cc[qu[cnt]] = 1;
	}
	return hh;
}

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