oj.uz

Submission #485840

# Submission time Handle Problem Language Result Execution time Memory
485840 2021-11-09T14:12:26 Z rainboy Grad (COI14_grad) C++17
100 / 100
 196 ms 75864 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB 41 numbers

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB 300 numbers

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB 500 numbers

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 46652 KB 15000 numbers
2 Correct 67 ms 46288 KB 15000 numbers
3 Correct 78 ms 39976 KB 30000 numbers

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 68556 KB 28333 numbers
2 Correct 112 ms 68292 KB 28333 numbers
3 Correct 131 ms 53240 KB 40000 numbers

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 66756 KB 50000 numbers
2 Correct 144 ms 66352 KB 50000 numbers
3 Correct 170 ms 66416 KB 50000 numbers

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 60468 KB 55000 numbers
2 Correct 129 ms 60036 KB 55000 numbers
3 Correct 149 ms 66444 KB 50000 numbers

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 66628 KB 50000 numbers
2 Correct 155 ms 67980 KB 50000 numbers
3 Correct 160 ms 67780 KB 50000 numbers
4 Correct 195 ms 68116 KB 50000 numbers

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 74416 KB 44000 numbers
2 Correct 158 ms 75864 KB 44000 numbers
3 Correct 147 ms 75736 KB 44000 numbers
4 Correct 161 ms 75796 KB 44000 numbers

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 66824 KB 50000 numbers
2 Correct 190 ms 68184 KB 50000 numbers
3 Correct 133 ms 67936 KB 50000 numbers
4 Correct 157 ms 68056 KB 50000 numbers

Subtask #11
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 72316 KB 45713 numbers
2 Correct 196 ms 62700 KB 54285 numbers
3 Correct 133 ms 56968 KB 58571 numbers
4 Correct 178 ms 59196 KB 57000 numbers

Subtask #12
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 67596 KB 49285 numbers
2 Correct 166 ms 68648 KB 49285 numbers
3 Correct 189 ms 68476 KB 49285 numbers
4 Correct 161 ms 74304 KB 45000 numbers