Submission #784245

#	Time	Username	Problem	Language	Result	Execution time	Memory
784245		rainboy	City Mapping (NOI18_citymapping)	C++17	100 / 100	8 ms	616 KiB

citymapping

#include "citymapping.h"
#include <stdio.h>
#include <stdlib.h>

const int N = 1000;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *ej[N], eo[N], jj[N], jj_[N]; long long dd[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
		while (j < k)
			if (dd[ii[j]] == dd[i_])
				j++;
			else if (dd[ii[j]] < dd[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

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 dfs(int i) {
	int s = 1, k_ = 0, j_ = -1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o], k = dfs(j);
		s += k;
		if (k_ < k)
			k_ = k, j_ = j;
	}
	jj[i] = j_;
	jj_[i] = j_ == -1 ? i : jj_[j_];
	return s;
}

void find_roads(int n, int q, int uu[], int vv[], int ww[]) {
	static int ii[N];
	for (int i = 1; i < n; i++)
		dd[i] = get_distance(1, i + 1);
	for (int i = 1; i < n; i++)
		ii[i] = i;
	sort(ii, 1, n);
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (int h = 1; h < n; h++) {
		int k = ii[h];
		dfs(0);
		int i = 0;
		while (1) {
			if (eo[i] == 0) {
				append(i, k);
				uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
				break;
			}
			long long d_ = (dd[jj_[i]] + dd[k] - get_distance(jj_[i] + 1, k + 1)) / 2;
			if (i != 0 || dd[i] < d_) {
				while (dd[i] < d_)
					i = jj[i];
				if (eo[i] <= 1) {
					append(i, k);
					uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
					break;
				}
				i = ej[i][0] ^ ej[i][1] ^ jj[i];
			} else {
				if (eo[i] == 1) {
					append(i, k);
					uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
					break;
				} else {
					int j = ej[i][0];
					if (j == jj[i])
						j = ej[i][1];
					long long d_ = (dd[jj_[j]] + dd[k] - get_distance(jj_[j] + 1, k + 1)) / 2;
					if (dd[i] < d_) {
						i = j;
						while (dd[i] < d_)
							i = jj[i];
						if (eo[i] <= 1) {
							append(i, k);
							uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
							break;
						}
						i = ej[i][0] ^ ej[i][1] ^ jj[i];
					} else {
						if (eo[i] == 2) {
							append(i, k);
							uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
							break;
						} else
							i = ej[i][0] ^ ej[i][1] ^ ej[i][2] ^ jj[i] ^ j;
					}
				}
			}
		}
	}
	for (int i = 0; i < n; i++)
		free(ej[i]);
}

Compilation message (stderr)

citymapping.cpp: In function 'void append(int, int)':
citymapping.cpp:35:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 43 / 43