oj.uz

Submission #904260

# Submission time Handle Problem Language Result Execution time Memory
904260 2024-01-12T01:54:10 Z rainboy Robot Race (CPSPC17_race) C
100 / 100
 2652 ms 79472 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	1000
#define M	1000
#define Q	1000000
#define INF	0x3f3f3f3f

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

void append(int **ej, int *eo, 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 tt[N * M + 1][2], pp[N * M + 1], sz[N * M + 1];

int dir(int u) {
	return tt[pp[u]][0] == u ? 0 : 1;
}

int is_root(int u) {
	return pp[u] == 0 || tt[pp[u]][dir(u)] != u;
}

void pul(int u) {
	sz[u] = sz[tt[u][0]] + sz[tt[u][1]] + 1;
}

void attach(int u, int v, int d) {
	if (u)
		tt[u][d] = v, pul(u);
	if (v)
		pp[v] = u;
}

void rotate(int u) {
	int v = pp[u], w = pp[v], du = dir(u), dv = dir(v), top = is_root(v);

	attach(v, tt[u][du ^ 1], du);
	attach(u, v, du ^ 1);
	if (top)
		pp[u] = w;
	else
		attach(w, u, dv);
}

void splay(int u) {
	while (!is_root(u)) {
		if (!is_root(pp[u]))
			rotate(dir(u) == dir(pp[u]) ? pp[u] : u);
		rotate(u);
	}
}

void expose(int u) {
	int v, w;

	for (v = u, w = 0; v; w = v, v = pp[v])
		splay(v), attach(v, w, 1);
	splay(u);
}

void link(int u, int v) {
	expose(v), expose(u);
	attach(u, v, 1);
}

void cut(int u, int v) {
	expose(v), expose(u);
	attach(u, 0, 1), pp[v] = 0;
}

int ancestor(int u, int k) {
	expose(u);
	while (1)
		if (k < sz[tt[u][1]])
			u = tt[u][1];
		else if (k > sz[tt[u][1]])
			k -= sz[tt[u][1]] + 1, u = tt[u][0];
		else {
			splay(u);
			return u;
		}
}

int main() {
	static char cc[N][M + 1];
	static int ii1[Q], jj1[Q], kk1[Q], ii2[Q], jj2[Q], kk2[Q], dp[N][M], dq[N][M], *eij[N + M], eo[N + M], *eh[N + M], eo_[N + M];
	static char active[N][M], yes[Q];
	int n, m, q, h, i, i1, i2, j, j1, j2, ij, k, k1, k2, r, o;

	scanf("%d%d%d", &n, &m, &q);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (h = 0; h < q; h++) {
		scanf("%d%d%d%d", &ii1[h], &jj1[h], &ii2[h], &jj2[h]), ii1[h]--, jj1[h]--, ii2[h]--, jj2[h]--;
		kk1[h] = ii1[h] + jj1[h], kk2[h] = ii2[h] + jj2[h];
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == '#')
				dp[i][j] = INF;
			else {
				dp[i][j] = i + j;
				if (i > 0)
					dp[i][j] = min(dp[i][j], dp[i - 1][j]);
				if (j > 0)
					dp[i][j] = min(dp[i][j], dp[i][j - 1]);
			}
	for (i = n - 1; i >= 0; i--)
		for (j = m - 1; j >= 0; j--)
			if (cc[i][j] == '#')
				dq[i][j] = -1;
			else {
				dq[i][j] = i + j;
				if (i + 1 < n)
					dq[i][j] = max(dq[i][j], dq[i + 1][j]);
				if (j + 1 < m)
					dq[i][j] = max(dq[i][j], dq[i][j + 1]);
			}
	for (k = 0; k < n + m; k++)
		eij[k] = (int *) malloc(2 * sizeof *eij[k]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == '.')
				append(eij, eo, dq[i][j], i * m + j);
	for (k = 0; k < n + m; k++)
		eh[k] = (int *) malloc(2 * sizeof *eh[k]);
	for (h = 0; h < q; h++) {
		i1 = ii1[h], j1 = jj1[h], k1 = kk1[h], i2 = ii2[h], j2 = jj2[h], k2 = kk2[h];
		if (k1 > k2 || dq[i1][j1] < k2 || dp[i2][j2] > k1)
			yes[h] = 0;
		else
			yes[h] = 1, append(eh, eo_, k2, h);
	}
	for (r = 0; r < 2; r++) {
		for (i = 0; i < n; i++)
			memset(active[i], 0, m * sizeof *active[i]);
		memset(pp, 0, (n * m + 1) * sizeof *pp);
		for (i = 1; i <= n * m; i++)
			tt[i][0] = tt[i][1] = 0, sz[i] = 1;
		for (k = n + m - 1; k >= 0; k--) {
			for (o = eo[k]; o--; ) {
				ij = eij[k][o], i = ij / m, j = ij % m;
				active[i][j] = 1;
				if (r == 0) {
					if (i + 1 < n && active[i + 1][j])
						link((i + 1) * m + j + 1, i * m + j + 1);
					else if (j + 1 < m && active[i][j + 1])
						link(i * m + (j + 1) + 1, i * m + j + 1);
					if (i > 0 && active[i - 1][j]) {
						if (j + 1 < m && active[i - 1][j + 1])
							cut((i - 1) * m + (j + 1) + 1, (i - 1) * m + j + 1);
						link(i * m + j + 1, (i - 1) * m + j + 1);
					}
					if (j > 0 && active[i][j - 1] && (i + 1 == n || !active[i + 1][j - 1]))
						link(i * m + j + 1, i * m + (j - 1) + 1);
				} else {
					if (j + 1 < m && active[i][j + 1])
						link(i * m + (j + 1) + 1, i * m + j + 1);
					else if (i + 1 < n && active[i + 1][j])
						link((i + 1) * m + j + 1, i * m + j + 1);
					if (j > 0 && active[i][j - 1]) {
						if (i + 1 < n && active[i + 1][j - 1])
							cut((i + 1) * m + (j - 1) + 1, i * m + (j - 1) + 1);
						link(i * m + j + 1, i * m + (j - 1) + 1);
					}
					if (i > 0 && active[i - 1][j] && (j + 1 == m || !active[i - 1][j + 1]))
						link(i * m + j + 1, (i - 1) * m + j + 1);
				}
			}
			for (o = eo_[k]; o--; ) {
				h = eh[k][o], i1 = ii1[h], j1 = jj1[h], k1 = kk1[h], i2 = ii2[h], j2 = jj2[h], k2 = kk2[h];
				ij = ancestor(i1 * m + j1 + 1, k2 - k1) - 1;
				if ((r == 0 ? ij < i2 * m + j2 : ij > i2 * m + j2))
					yes[h] = 0;
			}
		}
	}
	for (h = 0; h < q; h++)
		printf(yes[h] ? "YES\n" : "NO\n");
	return 0;
}

Compilation message

Main.c: In function 'append':
Main.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:98:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:100:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~
Main.c:102:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d%d%d%d", &ii1[h], &jj1[h], &ii2[h], &jj2[h]), ii1[h]--, jj1[h]--, ii2[h]--, jj2[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 41552 KB Output is correct
2 Correct 231 ms 41092 KB Output is correct
3 Correct 184 ms 41052 KB Output is correct
4 Correct 120 ms 40528 KB Output is correct
5 Correct 26 ms 37980 KB Output is correct
6 Correct 17 ms 37792 KB Output is correct
7 Correct 210 ms 41392 KB Output is correct
8 Correct 213 ms 41156 KB Output is correct
9 Correct 187 ms 40812 KB Output is correct
10 Correct 177 ms 40540 KB Output is correct
11 Correct 113 ms 40028 KB Output is correct
12 Correct 110 ms 39772 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 41552 KB Output is correct
2 Correct 231 ms 41092 KB Output is correct
3 Correct 184 ms 41052 KB Output is correct
4 Correct 120 ms 40528 KB Output is correct
5 Correct 26 ms 37980 KB Output is correct
6 Correct 17 ms 37792 KB Output is correct
7 Correct 210 ms 41392 KB Output is correct
8 Correct 213 ms 41156 KB Output is correct
9 Correct 187 ms 40812 KB Output is correct
10 Correct 177 ms 40540 KB Output is correct
11 Correct 113 ms 40028 KB Output is correct
12 Correct 110 ms 39772 KB Output is correct
13 Correct 2652 ms 63296 KB Output is correct
14 Correct 2163 ms 63060 KB Output is correct
15 Correct 744 ms 74520 KB Output is correct
16 Correct 370 ms 72376 KB Output is correct
17 Correct 269 ms 69972 KB Output is correct
18 Correct 274 ms 70104 KB Output is correct
19 Correct 2584 ms 79472 KB Output is correct
20 Correct 2375 ms 79372 KB Output is correct
21 Correct 2191 ms 78732 KB Output is correct
22 Correct 2025 ms 78420 KB Output is correct
23 Correct 1343 ms 76860 KB Output is correct
24 Correct 1135 ms 76156 KB Output is correct