Submission #1262197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262197		rainboy	World Map (IOI25_worldmap)	C++20	100 / 100	22 ms	2884 KiB

worldmap

#include "worldmap.h"
#include <cstdlib>
#include <cstring>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 40;

int max(int a, int b) { return a > b ? a : b; }

int n;

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int pp[N], dd[N], ta[N], tb[N], t_;

void dfs1(int p, int i, int d) {
	ta[i] = t_++;
	pp[i] = p, dd[i] = d;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (dd[j] == -1) {
			dfs1(i, j, d + 1);
			t_++;
		}
	}
	tb[i] = t_;
}

int cc[N * 2 - 1][N * 2 - 1];

void dfs2(int i) {
	for (int x = ta[i]; x < tb[i]; x++)
		for (int y = max(dd[i] * 2 - (x - ta[i]) % 2, 0); y < n * 2 - 1; y++)
			cc[x][y] = i + 1;
	int x = ta[i] + 1, y = dd[i] * 2;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (pp[j] == i)
			dfs2(j);
		else if (dd[j] > dd[i])
			cc[x][y] = j + 1, x += 2;
	}
}

vvi create_map(int n_, int m, vi ii, vi jj) {
	n = n_;
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (int h = 0; h < m; h++) {
		int i = ii[h] - 1, j = jj[h] - 1;
		append(i, j), append(j, i);
	}
	memset(dd, -1, n * sizeof *dd);
	t_ = 0, dfs1(-1, 0, 0);
	dfs2(0);
	vvi cc_(n * 2 - 1, vi(n * 2 - 1, 0));
	for (int x = 0; x < n * 2 - 1; x++)
		for (int y = 0; y < n * 2 - 1; y++)
			cc_[x][y] = cc[x][y];
	for (int i = 0; i < n; i++)
		free(ej[i]);
  return cc_;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 56 / 56