QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504694#9108. Zayin and Obstaclesuntitledtwo#AC ✓218ms12816kbC++202.1kb2024-08-04 14:55:312024-08-04 14:55:32

Judging History

你现在查看的是最新测评结果

  • [2024-08-04 14:55:32]
  • 评测
  • 测评结果:AC
  • 用时:218ms
  • 内存:12816kb
  • [2024-08-04 14:55:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;

int n, m;
int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {0, 0, 0, 0, 1, -1};
int dz[6] = {1, -1, 0, 0, 0, 0};
struct Node{
	int x, y, z;
};
queue<Node> que;
int dist[105][105][105], s[105][105][105];

int check(Node q) {
	int x = q.x, y = q.y, z = q.z;
	if (x < 1 || x > n || y < 1 || y > n || z < 1 || z > n) return 0;
	if (s[x][y][z] != 0) return 0;
	return 1;
}
void solve() {
	for (int i = 1; i <= n ; ++ i)
		for (int j = 1; j <= n ; ++ j)
			for (int k = 1; k <= n ; ++ k)
				s[i][j][k] += s[i - 1][j][k];
	for (int i = 1; i <= n ; ++ i)
		for (int j = 1; j <= n ; ++ j)
			for (int k = 1; k <= n ; ++ k)
				s[i][j][k] += s[i][j - 1][k];
	for (int i = 1; i <= n ; ++ i)
		for (int j = 1; j <= n ; ++ j)
			for (int k = 1; k <= n ; ++ k)
				s[i][j][k] += s[i][j][k - 1];
}
signed main() {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
#endif
	int Case;
	scanf("%d", &Case);
	while (Case --) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n ; ++ i)
			for (int j = 1; j <= n ; ++ j)
				for (int k = 1; k <= n ; ++ k) s[i][j][k] = 0, dist[i][j][k] = INF;
		for (int i = 1; i <= m ; ++ i) {
			int l1, l2, l3, r1, r2, r3;
			scanf("%d%d%d%d%d%d", &l1, &l2, &l3, &r1, &r2, &r3);
			++ s[l1][l2][l3];

			-- s[r1 + 1][l2][l3];
			-- s[l1][r2 + 1][l3];
			-- s[l1][l2][r3 + 1];

			++ s[r1 + 1][r2 + 1][l3];
			++ s[l1][r2 + 1][r3 + 1];
			++ s[r1 + 1][l2][r3 + 1];

			-- s[r1 + 1][r2 + 1][r3 + 1];
		}
		solve();
		int X, Y, Z;
		scanf("%d%d%d", &X, &Y, &Z);
		que.push((Node){X, Y, Z}), dist[X][Y][Z] = 0;
		while (!que.empty()) {
			Node q = que.front(); que.pop();
			for (int i = 0; i < 6 ; ++ i) {
				Node p = (Node){q.x + dx[i], q.y + dy[i], q.z + dz[i]};
				if (check(p) && dist[p.x][p.y][p.z] == INF) 
					dist[p.x][p.y][p.z] = dist[q.x][q.y][q.z] + 1, que.push(p);
			}
		}
		scanf("%d%d%d", &X, &Y, &Z);
		if (dist[X][Y][Z] == INF) printf("-1\n");
		else printf("%d\n", dist[X][Y][Z]);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5836kb

input:

3
3 0
1 1 1 3 3 3
3 1
2 1 1 2 3 3
1 1 1 3 3 3
3 3
2 1 1 2 2 3
1 1 2 2 3 2
1 2 2 3 3 2
1 1 1 1 1 3

output:

6
-1
14

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 18ms
memory: 12588kb

input:

5
19 27
2 1 1 2 18 19
4 2 1 4 19 19
6 1 1 6 18 19
8 2 1 8 19 19
10 1 1 10 18 19
12 2 1 12 19 19
14 1 1 14 18 19
16 2 1 16 19 19
18 1 1 18 18 19
1 1 2 18 19 2
2 1 4 19 19 4
1 1 6 18 19 6
2 1 8 19 19 8
1 1 10 18 19 10
2 1 12 19 19 12
1 1 14 18 19 14
2 1 16 19 19 16
1 1 18 18 19 18
1 2 2 19 19 2
1 2 4 ...

output:

1998
15998
53998
127998
249998

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 52ms
memory: 12584kb

input:

5
99 147
2 1 1 2 98 99
4 2 1 4 99 99
6 1 1 6 98 99
8 2 1 8 99 99
10 1 1 10 98 99
12 2 1 12 99 99
14 1 1 14 98 99
16 2 1 16 99 99
18 1 1 18 98 99
20 2 1 20 99 99
22 1 1 22 98 99
24 2 1 24 99 99
26 1 1 26 98 99
28 2 1 28 99 99
30 1 1 30 98 99
32 2 1 32 99 99
34 1 1 34 98 99
36 2 1 36 99 99
38 1 1 38 9...

output:

132878
2596
227782
37198
90672

result:

ok 5 lines

Test #4:

score: 0
Accepted
time: 19ms
memory: 12816kb

input:

5
99 1000
2 1 1 2 98 99
4 2 1 4 99 99
6 1 1 6 98 99
8 2 1 8 99 99
10 1 1 10 98 99
12 2 1 12 99 99
14 1 1 14 98 99
16 2 1 16 99 99
18 1 1 18 98 99
20 2 1 20 99 99
22 1 1 22 98 99
24 2 1 24 99 99
26 1 1 26 98 99
28 2 1 28 99 99
30 1 1 30 98 99
32 2 1 32 99 99
34 1 1 34 98 99
36 2 1 36 99 99
38 1 1 38 ...

output:

4998
4998
4998
4998
4998

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 36ms
memory: 12512kb

input:

5
19 1000
2 1 1 2 18 19
4 2 1 4 19 19
6 1 1 6 18 19
8 2 1 8 19 19
10 1 1 10 18 19
12 2 1 12 19 19
14 1 1 14 18 19
16 2 1 16 19 19
18 1 1 18 18 19
4 13 10 4 19 12
6 5 5 6 6 18
6 16 4 6 18 11
8 6 10 8 17 19
14 10 7 14 17 12
2 4 4 2 5 15
4 5 10 4 7 17
12 1 2 12 2 9
12 8 10 12 18 15
16 19 2 16 19 8
8 1 ...

output:

-1
798
1906
3198
4998

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 218ms
memory: 12784kb

input:

5
100 0
92 81 37 11 85 14
100 0
16 48 91 61 65 58
100 0
87 25 52 83 7 45
100 0
80 95 16 62 5 80
100 0
33 33 50 48 82 3

output:

108
95
29
172
111

result:

ok 5 lines