oj.uz

답안 #904258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
904258 2024-01-12T01:44:12 Z rainboy Robot Race (CPSPC17_race) C
20 / 100
 2417 ms 79512 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 * 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

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 41140 KB Output is correct
2 Correct 226 ms 41068 KB Output is correct
3 Correct 176 ms 41048 KB Output is correct
4 Correct 89 ms 41096 KB Output is correct
5 Correct 27 ms 39004 KB Output is correct
6 Correct 18 ms 38492 KB Output is correct
7 Correct 212 ms 42324 KB Output is correct
8 Correct 198 ms 42104 KB Output is correct
9 Correct 180 ms 41820 KB Output is correct
10 Correct 169 ms 41552 KB Output is correct
11 Correct 102 ms 41300 KB Output is correct
12 Correct 85 ms 40788 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 41140 KB Output is correct
2 Correct 226 ms 41068 KB Output is correct
3 Correct 176 ms 41048 KB Output is correct
4 Correct 89 ms 41096 KB Output is correct
5 Correct 27 ms 39004 KB Output is correct
6 Correct 18 ms 38492 KB Output is correct
7 Correct 212 ms 42324 KB Output is correct
8 Correct 198 ms 42104 KB Output is correct
9 Correct 180 ms 41820 KB Output is correct
10 Correct 169 ms 41552 KB Output is correct
11 Correct 102 ms 41300 KB Output is correct
12 Correct 85 ms 40788 KB Output is correct
13 Correct 2417 ms 79512 KB Output is correct
14 Incorrect 1913 ms 79168 KB Output isn't correct
15 Halted 0 ms 0 KB -