제출 #1124952

#제출 시각아이디문제언어결과실행 시간메모리
1124952TrendBattlesWall (CEOI14_wall)C++17
100 / 100
374 ms62340 KiB
#include <bits/stdc++.h> using namespace std; using lli = int64_t; #define INFILE "steelwall.inp" #define OUTFILE "steelwall.out" const int MAX_N = 410; lli dist[MAX_N * MAX_N * 4 + 10]; vector <pair <int, int>> graph[MAX_N * MAX_N * 4 + 10]; int resident[MAX_N][MAX_N]; int row_cost[MAX_N][MAX_N], col_cost[MAX_N][MAX_N]; void add_edge(int u, int v, int w) { graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); } template <class T> using MinHeap = priority_queue <T, vector <T>, greater <T>>; int minimise(lli& x, lli y) { if (x > y) return x = y, true; return false; } void Dijkstra(int source) { memset(dist, 0x3f, sizeof dist); dist[source] = 0; MinHeap <pair <lli, int>> heap; heap.emplace(0, source); while (not heap.empty()) { lli d; int u; tie(d, u) = heap.top(); heap.pop(); if (d != dist[u]) continue; for (pair <int, int>& E : graph[u]) { int v, w; tie(v, w) = E; if (minimise(dist[v], dist[u] + w)) { heap.emplace(dist[v], v); } } } } void reset() { for (int i = 0; i <= MAX_N * MAX_N; ++i) { graph[i].clear(); graph[i].shrink_to_fit(); } } #define ID(i, j) ((i) * (M + 1) + (j)) int banned_down[MAX_N][MAX_N], banned_right[MAX_N][MAX_N]; int visited[MAX_N * MAX_N + 10]; int main() { ios::sync_with_stdio(0); cin.tie(0); if (fopen(INFILE, "r")) { freopen(INFILE, "r", stdin); freopen(OUTFILE, "w", stdout); } int N, M; cin >> N >> M; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { cin >> resident[i][j]; } } for (int i = 0; i < N; ++i) { for (int j = 0; j <= M; ++j) { cin >> row_cost[i][j]; add_edge(ID(i, j), ID(i + 1, j), row_cost[i][j]); } } for (int i = 0; i <= N; ++i) { for (int j = 0; j < M; ++j) { cin >> col_cost[i][j]; add_edge(ID(i, j), ID(i, j + 1), col_cost[i][j]); } } Dijkstra(0); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { if (resident[i][j]) { banned_down[i - 1][j - 1] = banned_down[i - 1][j] = banned_right[i - 1][j - 1] = banned_right[i][j - 1] = true; } } } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { if (not resident[i][j]) continue; queue <int> q; q.push(ID(i, j)); while (not q.empty()) { int c_id = q.front(); q.pop(); if (visited[c_id]) continue; visited[c_id] = true; if (c_id == 0) continue; for (pair <int, int>& E : graph[c_id]) { int p_id, w; tie(p_id, w) = E; if (dist[p_id] + w != dist[c_id]) continue; q.push(p_id); int x = c_id / (M + 1), y = c_id % (M + 1); int u = p_id / (M + 1), v = p_id % (M + 1); if (x + 1 == u) { banned_down[x][y] = true; } if (x - 1 == u) { banned_down[u][v] = true; } if (y + 1 == v) { banned_right[x][y] = true; } if (y - 1 == v) { banned_right[u][v] = true; } break; } } } } reset(); for (int i = 0; i < N; ++i) { for (int j = 0; j <= M; ++j) { for (int d = 0; d < 2; ++d) { add_edge(ID(i, j) * 4 + d + 2, ID(i + 1, j) * 4 + d, row_cost[i][j]); } if (not banned_down[i][j]) { add_edge(ID(i, j) * 4 + 2, ID(i, j) * 4 + 3, 0); add_edge(ID(i + 1, j) * 4 + 0, ID(i + 1, j) * 4 + 1, 0); } } } for (int i = 0; i <= N; ++i) { for (int j = 0; j < M; ++j) { for (int d : {1, 3}) { add_edge(ID(i, j) * 4 + d, ID(i, j + 1) * 4 + d - 1, col_cost[i][j]); } if (not banned_right[i][j]) { add_edge(ID(i, j) * 4 + 1, ID(i, j) * 4 + 3, 0); add_edge(ID(i, j + 1) * 4 + 0, ID(i, j + 1) * 4 + 2, 0); } } } for (int i = 0; i <= N; ++i) { for (int j = 0; j <= M; ++j) { if (i == 0 and j == 0) continue; if (i == 0) { add_edge(ID(i, j) * 4 + 0, ID(i, j) * 4 + 1, 0); } if (i == N) { add_edge(ID(i, j) * 4 + 2, ID(i, j) * 4 + 3, 0); } if (j == 0) { add_edge(ID(i, j) * 4 + 0, ID(i, j) * 4 + 2, 0); } if (j == M) { add_edge(ID(i, j) * 4 + 1, ID(i, j) * 4 + 3, 0); } } } Dijkstra(ID(0, 0) * 4 + 1); cout << dist[ID(0, 0) * 4 + 2]; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In function 'int main()':
wall.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
wall.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...