oj.uz

답안 #536689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536689 2022-03-13T21:36:02 Z LucaDantas Wall (CEOI14_wall) C++17
10 / 100
 95 ms 13420 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 410;

int village[maxn][maxn]; // represents wether there is a village
pair<int,int> pai[maxn][maxn]; // represents the edge it came from on the first dijsktra

int horizontal[maxn][maxn], vertical[maxn][maxn];
bool blue_h[maxn][maxn], blue_v[maxn][maxn];

int n, m;

long long dist[maxn][maxn];
bool mark[maxn][maxn];

// que negocio feio
void dijkstra1() {
	memset(dist, 0x3f, sizeof dist);
	dist[1][1] = 0;
	priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> q;
	q.push({0, 1, 1});

	while(q.size()) {
		auto [trash, x, y] = q.top(); q.pop();

		if(mark[x][y]) continue; mark[x][y] = 1;

		// [x][y] -> [x][y+1]
		if(y+1 <= m+1 && dist[x][y] + horizontal[x][y] < dist[x][y+1]) {
			dist[x][y+1] = dist[x][y] + horizontal[x][y];
			pai[x][y+1] = {x, y};
			q.push({dist[x][y+1], x, y+1});
		}
		// [x][y] -> [x][y-1]
		if(y-1 >= 1 && dist[x][y] + horizontal[x][y-1] < dist[x][y-1]) {
			dist[x][y-1] = dist[x][y] + horizontal[x][y-1];
			pai[x][y-1] = {x, y};
			q.push({dist[x][y-1], x, y-1});
		}
		// [x][y] -> [x+1][y]
		if(x+1 <= n+1 && dist[x][y] + vertical[x][y] < dist[x+1][y]) {
			dist[x+1][y] = dist[x][y] + vertical[x][y];
			pai[x+1][y] = {x, y};
			q.push({dist[x+1][y], x+1, y});
		}
		// [x][y] -> [x-1][y]
		if(x-1 >= 1 && dist[x][y] + vertical[x-1][y] < dist[x-1][y]) {
			dist[x-1][y] = dist[x][y] + vertical[x-1][y];
			pai[x-1][y] = {x, y};
			q.push({dist[x-1][y], x-1, y});
		}

	}
}

void go(int r, int c) {
	if(r == 1 && c == 1) return;
	if(pai[r][c] == pair<int,int>(r-1, c) && !blue_v[r-1][c]) {
		blue_v[r-1][c] = 1;
		go(r-1, c);
	} else if(pai[r][c] == pair<int,int>(r+1, c) && !blue_v[r][c]) {
		blue_v[r][c] = 1;
		go(r+1, c);
	} else if(pai[r][c] == pair<int,int>(r, c-1) && !blue_h[r][c-1]) {
		blue_h[r][c-1] = 1;
		go(r, c-1);
	} else if(pai[r][c] == pair<int,int>(r, c+1) && !blue_h[r][c]) {
		blue_h[r][c] = 1;
		go(r, c+1);
	}
}

void mark_blue() {
	// pinto os arredores de todas as vilas como azuis
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(village[i][j]) go(i, j); // pinto o menor caminho de mim até a raiz de azul

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(village[i][j]) {
				blue_h[i][j] = 1;
				blue_v[i][j] = 1;
				blue_h[i+1][j] = 1;
				blue_v[i][j+1] = 1;
			}
		}
	}

	// arestas especiais -> se eu nao colocar isso o cara pode simplesmente cruzar pelo canto superior esquerdo e a resposta vai ser 0
	blue_v[0][1] = 1;
	blue_h[1][0] = 1;
}

vector<pair<int,int>> g[4*maxn]; // meu indice é == 4*((i-1)*(m+1) + (j-1)) + id_quadrado

// id_quadrado:
// 00 == 0 -> left_up
// 01 == 1 -> right_up
// 10 == 2 -> left_down
// 11 == 3 -> right_down

void create_edges() {
	// arestas entre subpontos do mesmo ponto
	for(int i = 1; i <= n+1; i++) {
		for(int j = 1; j <= m+1; j++) {
			int id = 4*((i-1)*(m+1) + (j-1)); // id base pros proximos (vou somar id_qd pra obter o valor real)
			if(!blue_v[i-1][j]) // linha vindo de [i-1][j] -> [i][j]
				g[id].push_back({id+1, 0}), g[id+1].push_back({id, 0});
			
			if(!blue_v[i][j]) // linha [i][j] -> [i+1][j]
				g[id+2].push_back({id+3, 0}), g[id+3].push_back({id+2, 0});

			if(!blue_h[i][j-1]) // linha [i][j-1] -> [i][j]
				g[id].push_back({id+2, 0}), g[id+2].push_back({id, 0});

			if(!blue_h[i][j]) // linha [i][j] -> [i][j+1]
				g[id+1].push_back({id+3, 0}), g[id+3].push_back({id+1, 0});
		}
	}

	auto get = [](int i, int j) { return 4*((i-1)*(m+1) + (j-1)); };
	auto valid = [](int i, int j) { return i >= 1 && i <= n+1 && j >= 1 && j <= m+1; };

	// arestas entre subpontos de pontos diferentes (tem peso)
	for(int i = 1; i <= n+1; i++) {
		for(int j = 1; j <= m+1; j++) {
			int id = get(i, j);

			if(valid(i-1, j)) // [i-1][j] -> [i][j]
				g[id].push_back({get(i-1, j) + 2, vertical[i-1][j]}),
				g[id+1].push_back({get(i-1, j) + 3, vertical[i-1][j]});
			
			if(valid(i+1, j)) // [i][j] -> [i+1][j]
				g[id+2].push_back({get(i+1, j), vertical[i][j]}),
				g[id+3].push_back({get(i+1, j)+1, vertical[i][j]});
			
			if(valid(i, j-1)) // [i][j-1] -> [i][j]
				g[id].push_back({get(i, j-1)+1, horizontal[i][j-1]}),
				g[id+2].push_back({get(i, j-1)+3, horizontal[i][j-1]});

			if(valid(i, j+1)) // [i][j] -> [i][j+1]
				g[id+1].push_back({get(i, j+1), horizontal[i][j]}),
				g[id+3].push_back({get(i, j+1)+2, horizontal[i][j]});
		}
	}
}

long long dist2[maxn*maxn*4];
bool mark2[maxn*maxn*4];

void dijkstra2() {
	memset(dist2, 0x3f, sizeof dist2);
	priority_queue<pair<long long,int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

	dist2[1] = 0; // 1 é o quadrado superior direito de [1][1]
	
	q.push({0, 1});
	
	while(q.size()) {
		int u = q.top().second; q.pop();
		if(mark2[u]) continue; mark2[u] = 1;

		for(auto [v, w] : g[u]) {
			if(dist2[v] > dist2[u] + w) {
				dist2[v] = dist2[u] + w;
				q.push({dist2[v], v});
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%d", &village[i][j]);

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m+1; j++)
			scanf("%d", &vertical[i][j]); // the edge from [i][j] to [i+1][j], [i][j] represents the top left square
	
	for(int i = 1; i <= n+1; i++)
		for(int j = 1; j <= m; j++)
			scanf("%d", &horizontal[i][j]); // [i][j] to [i][j+1]

	dijkstra1();

	mark_blue();

	create_edges();

	dijkstra2();

	printf("%lld\n", dist2[2]);
}

Compilation message

wall.cpp: In function 'void dijkstra1()':
wall.cpp:27:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |   if(mark[x][y]) continue; mark[x][y] = 1;
      |   ^~
wall.cpp:27:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |   if(mark[x][y]) continue; mark[x][y] = 1;
      |                            ^~~~
wall.cpp: In function 'void dijkstra2()':
wall.cpp:164:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  164 |   if(mark2[u]) continue; mark2[u] = 1;
      |   ^~
wall.cpp:164:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  164 |   if(mark2[u]) continue; mark2[u] = 1;
      |                          ^~~~~
wall.cpp: In function 'int main()':
wall.cpp:176:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:179:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |    scanf("%d", &village[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wall.cpp:183:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |    scanf("%d", &vertical[i][j]); // the edge from [i][j] to [i+1][j], [i][j] represents the top left square
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:187:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |    scanf("%d", &horizontal[i][j]); // [i][j] to [i][j+1]
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7016 KB Output is correct
2 Correct 4 ms 7020 KB Output is correct
3 Correct 3 ms 6976 KB Output is correct
4 Correct 3 ms 6996 KB Output is correct
5 Correct 5 ms 6996 KB Output is correct
6 Runtime error 3 ms 3924 KB Execution killed with signal 11
7 Runtime error 5 ms 3796 KB Execution killed with signal 11
8 Runtime error 5 ms 3924 KB Execution killed with signal 11
9 Runtime error 5 ms 3796 KB Execution killed with signal 11
10 Runtime error 4 ms 3872 KB Execution killed with signal 11
11 Runtime error 4 ms 3984 KB Execution killed with signal 11
12 Runtime error 4 ms 4052 KB Execution killed with signal 11
13 Runtime error 3 ms 4052 KB Execution killed with signal 11
14 Runtime error 4 ms 4092 KB Execution killed with signal 11
15 Runtime error 4 ms 3924 KB Execution killed with signal 11

Subtask #2
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 4052 KB Execution killed with signal 11
2 Runtime error 4 ms 4052 KB Execution killed with signal 11
3 Runtime error 3 ms 4084 KB Execution killed with signal 11
4 Runtime error 4 ms 4052 KB Execution killed with signal 11
5 Runtime error 4 ms 4084 KB Execution killed with signal 11
6 Runtime error 4 ms 4060 KB Execution killed with signal 11
7 Runtime error 3 ms 4052 KB Execution killed with signal 11
8 Runtime error 4 ms 4060 KB Execution killed with signal 11
9 Runtime error 5 ms 4052 KB Execution killed with signal 11
10 Runtime error 5 ms 4052 KB Execution killed with signal 11
11 Runtime error 4 ms 4052 KB Execution killed with signal 11
12 Runtime error 7 ms 4220 KB Execution killed with signal 11
13 Runtime error 4 ms 4052 KB Execution killed with signal 11
14 Runtime error 4 ms 4136 KB Execution killed with signal 11
15 Runtime error 3 ms 4052 KB Execution killed with signal 11
16 Runtime error 4 ms 4052 KB Execution killed with signal 11
17 Runtime error 4 ms 4052 KB Execution killed with signal 11
18 Runtime error 4 ms 4052 KB Execution killed with signal 11

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 7608 KB Execution killed with signal 11
2 Runtime error 17 ms 6932 KB Execution killed with signal 11
3 Runtime error 17 ms 7176 KB Execution killed with signal 11
4 Runtime error 18 ms 7332 KB Execution killed with signal 11
5 Runtime error 52 ms 10080 KB Execution killed with signal 11
6 Runtime error 23 ms 7500 KB Execution killed with signal 11
7 Runtime error 54 ms 10228 KB Execution killed with signal 11
8 Runtime error 45 ms 9724 KB Execution killed with signal 11
9 Runtime error 37 ms 9968 KB Execution killed with signal 11
10 Runtime error 43 ms 10284 KB Execution killed with signal 11
11 Runtime error 43 ms 10744 KB Execution killed with signal 11
12 Runtime error 21 ms 7548 KB Execution killed with signal 11
13 Runtime error 45 ms 9992 KB Execution killed with signal 11
14 Runtime error 82 ms 11972 KB Execution killed with signal 11
15 Runtime error 78 ms 11916 KB Execution killed with signal 11
16 Runtime error 65 ms 12876 KB Execution killed with signal 11
17 Runtime error 71 ms 13204 KB Execution killed with signal 11
18 Runtime error 78 ms 13420 KB Execution killed with signal 11
19 Runtime error 90 ms 12632 KB Execution killed with signal 11
20 Runtime error 95 ms 12900 KB Execution killed with signal 11