Submission #485840

#	Time	Username	Problem	Language	Result	Execution time	Memory
485840		rainboy	Grad (COI14_grad)	C++17	100 / 100	196 ms	75864 KiB

grad

#include <math.h>
#include <stdio.h>

#define N	100100
#define M	(N * 2)
#define L	17	/* L = floor(log2(M)) */
#define INF	1e13

double min(double a, double b) { return a < b ? a : b; }

int xx[N], yy[N], hh[N], n;
int ii[M], jj[M], dd[M], pp[M][L + 1], m; double ddd[M][L + 1][2][2];

int find(int i, int j) {
	int lower = -1, upper = m;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (ii[h] < i || ii[h] == i && jj[h] <= j)
			lower = h;
		else
			upper = h;
	}
	return lower;
}

void add(int p, int i, int j) {
	int h = m++, a, b, c, l;

	hh[i] = hh[j] = h;
	ii[h] = i, jj[h] = j, dd[h] = p == -1 ? 0 : dd[p] + 1;
	pp[h][0] = p;
	if (dd[h] > 0) {
		for (a = 0; a < 2; a++)
			for (b = 0; b < 2; b++) {
				int u = a == 0 ? ii[h] : jj[h], v = b == 0 ? ii[p] : jj[p];

				ddd[h][0][a][b] = hypot(xx[u] - xx[v], yy[u] - yy[v]);
			}
		for (l = 1; 1 << l <= dd[h]; l++) {
			int p = pp[h][l - 1];

			pp[h][l] = pp[p][l - 1];
			for (a = 0; a < 2; a++)
				for (b = 0; b < 2; b++)
					ddd[h][l][a][b] = INF;
			for (a = 0; a < 2; a++)
				for (b = 0; b < 2; b++)
					for (c = 0; c < 2; c++)
						ddd[h][l][a][c] = min(ddd[h][l][a][c], ddd[h][l - 1][a][b] + ddd[p][l - 1][b][c]);
		}
	}
}

double query(int i, int j) {
	static double ddi[2], ddi_[2], ddj[2], ddj_[2];
	int tmp, h1, h2, l, a, b;
	double d;

	if (dd[hh[i]] < dd[hh[j]])
		tmp = i, i = j, j = tmp;
	h1 = hh[i], h2 = hh[j];
	if (i == ii[h1])
		ddi[0] = 0, ddi[1] = hypot(xx[ii[h1]] - xx[jj[h1]], yy[ii[h1]] - yy[jj[h1]]);
	else
		ddi[0] = hypot(xx[ii[h1]] - xx[jj[h1]], yy[ii[h1]] - yy[jj[h1]]), ddi[1] = 0;
	if (j == ii[h2])
		ddj[0] = 0, ddj[1] = hypot(xx[ii[h2]] - xx[jj[h2]], yy[ii[h2]] - yy[jj[h2]]);
	else
		ddj[0] = hypot(xx[ii[h2]] - xx[jj[h2]], yy[ii[h2]] - yy[jj[h2]]), ddj[1] = 0;
	for (l = L; l >= 0; l--)
		if (dd[h1] - dd[h2] >= 1 << l) {
			for (a = 0; a < 2; a++)
				ddi_[a] = INF;
			for (a = 0; a < 2; a++)
				for (b = 0; b < 2; b++)
					ddi_[b] = min(ddi_[b], ddi[a] + ddd[h1][l][a][b]);
			for (a = 0; a < 2; a++)
				ddi[a] = ddi_[a];
			h1 = pp[h1][l];
		}
	if (h1 == h2)
		return ddi[j == ii[h2] ? 0 : 1];
	for (l = L; l >= 0; l--)
		if (dd[h1] >= 1 << l && pp[h1][l] != pp[h2][l]) {
			for (a = 0; a < 2; a++)
				ddi_[a] = INF;
			for (a = 0; a < 2; a++)
				for (b = 0; b < 2; b++)
					ddi_[b] = min(ddi_[b], ddi[a] + ddd[h1][l][a][b]);
			for (a = 0; a < 2; a++)
				ddi[a] = ddi_[a];
			for (a = 0; a < 2; a++)
				ddj_[a] = INF;
			for (a = 0; a < 2; a++)
				for (b = 0; b < 2; b++)
					ddj_[b] = min(ddj_[b], ddj[a] + ddd[h2][l][a][b]);
			for (a = 0; a < 2; a++)
				ddj[a] = ddj_[a];
			h1 = pp[h1][l], h2 = pp[h2][l];
		}
	d = INF;
	for (a = 0; a < 2; a++)
		for (b = 0; b < 2; b++) {
			int u = a == 0 ? ii[h1] : jj[h1], v = b == 0 ? ii[h2] : jj[h2];

			if (u == v)
				d = min(d, ddi[a] + ddj[b]);
		}
	for (a = 0; a < 2; a++)
		ddi_[a] = INF;
	for (a = 0; a < 2; a++)
		for (b = 0; b < 2; b++)
			ddi_[b] = min(ddi_[b], ddi[a] + ddd[h1][0][a][b]);
	for (a = 0; a < 2; a++)
		ddi[a] = ddi_[a];
	for (a = 0; a < 2; a++)
		ddj_[a] = INF;
	for (a = 0; a < 2; a++)
		for (b = 0; b < 2; b++)
			ddj_[b] = min(ddj_[b], ddj[a] + ddd[h2][0][a][b]);
	for (a = 0; a < 2; a++)
		ddj[a] = ddj_[a];
	d = min(d, min(ddi[0] + ddj[0], ddi[1] + ddj[1]));
	return d;
}

int main() {
	int q;

	scanf("%d%d%d%d%d", &xx[0], &yy[0], &xx[1], &yy[1], &q), n = 2;
	add(-1, 1, 0);
	while (q--) {
		static char s[2];
		int i, j;

		scanf("%s", s);
		if (s[0] == 'd') {
			int h, tmp;

			scanf("%d%d%d%d", &xx[n], &yy[n], &i, &j), i--, j--;
			if (i > j)
				tmp = i, i = j, j = tmp;
			h = find(j, i);
			add(h, n, i), add(h, n, j), n++;
		} else {
			scanf("%d%d", &i, &j), i--, j--;
			printf("%f\n", query(i, j));
		}
	}
	return 0;
}

Compilation message (stderr)

grad.cpp: In function 'int find(int, int)':
grad.cpp:20:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |   if (ii[h] < i || ii[h] == i && jj[h] <= j)
      |                    ~~~~~~~~~~~^~~~~~~~~~~~~
grad.cpp: In function 'int main()':
grad.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |  scanf("%d%d%d%d%d", &xx[0], &yy[0], &xx[1], &yy[1], &q), n = 2;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grad.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |   scanf("%s", s);
      |   ~~~~~^~~~~~~~~
grad.cpp:142:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |    scanf("%d%d%d%d", &xx[n], &yy[n], &i, &j), i--, j--;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grad.cpp:148:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |    scanf("%d%d", &i, &j), i--, j--;
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 6 / 6
• Subtask 7: 6 / 6
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11
• Subtask 11: 11 / 11
• Subtask 12: 11 / 11