제출 #624334

#제출 시각아이디문제언어결과실행 시간메모리
624334GusterGoose27Wall (CEOI14_wall)C++11
100 / 100
769 ms81568 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<pii, int> edge; const int MAXN = 405; const ll inf = 1e18; ll dist[MAXN][MAXN]; int n, m; pii par[MAXN][MAXN]; int path_mask[MAXN][MAXN]; // right, up, left, down vector<edge> edges[MAXN][MAXN]; // node, weight bool village[MAXN][MAXN]; vector<pii> village_list; bool pruned[MAXN][MAXN]; vector<pii> expans_graph[4*MAXN*MAXN]; ll dist2[4*MAXN*MAXN]; struct comp { bool operator()(const pii &a, const pii &b) { return (dist[a.first][a.second] == dist[b.first][b.second]) ? (a < b) : (dist[a.first][a.second] < dist[b.first][b.second]); } }; struct comp2 { bool operator()(const int &a, const int &b) { return (dist2[a] == dist2[b]) ? (a < b) : (dist2[a] < dist2[b]); } }; int hsh(int i, int j, int d) { return 4*(i*(m+1)+j)+d; } void dijkstra() { set<pii, comp> pq; dist[0][0] = 0; pq.insert(pii(0, 0)); while (!pq.empty()) { pii cur = *(pq.begin()); pq.erase(cur); ll curdist = dist[cur.first][cur.second]; for (edge e: edges[cur.first][cur.second]) { pii next = e.first; if (curdist + e.second < dist[next.first][next.second]) { pq.erase(next); dist[next.first][next.second] = curdist + e.second; par[next.first][next.second] = cur; pq.insert(next); } } } } void dijkstra2() { set<int, comp2> pq; dist2[hsh(0, 0, 0)] = 0; pq.insert(0); while (!pq.empty()) { int cur = *(pq.begin()); pq.erase(cur); for (pii p: expans_graph[cur]) { int next = p.first; if (dist2[cur]+p.second < dist2[next]) { pq.erase(next); dist2[next] = dist2[cur]+p.second; pq.insert(next); } } } } void prune(pii cur) { if (pruned[cur.first][cur.second]) return; pruned[cur.first][cur.second] = 1; pii parent = par[cur.first][cur.second]; if (parent.first == cur.first && parent.second == cur.second-1) { // left path_mask[parent.first][parent.second] |= 1; path_mask[cur.first][cur.second] |= 4; } if (parent.first == cur.first && parent.second == cur.second+1) { // right path_mask[parent.first][parent.second] |= 4; path_mask[cur.first][cur.second] |= 1; } if (parent.first == cur.first-1 && parent.second == cur.second) { // up path_mask[parent.first][parent.second] |= 8; path_mask[cur.first][cur.second] |= 2; } if (parent.first == cur.first+1 && parent.second == cur.second) { // down path_mask[parent.first][parent.second] |= 2; path_mask[cur.first][cur.second] |= 8; } prune(parent); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 0; i <= n; i++) fill(dist[i], dist[i]+m+1, inf); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> village[i][j]; if (village[i][j]) village_list.push_back(pii(i, j)); } } for (int i = 0; i < n; i++) { for (int j = 0; j <= m; j++) { int v; cin >> v; edges[i][j].push_back(edge(pii(i+1, j), v)); edges[i+1][j].push_back(edge(pii(i, j), v)); int hsh1 = hsh(i, j, 3); int hsh2 = hsh(i+1, j, 1); expans_graph[hsh(i, j, 3)].push_back(pii(hsh(i+1, j, 0), v)); expans_graph[hsh(i, j, 2)].push_back(pii(hsh(i+1, j, 1), v)); expans_graph[hsh(i+1, j, 0)].push_back(pii(hsh(i, j, 3), v)); expans_graph[hsh(i+1, j, 1)].push_back(pii(hsh(i, j, 2), v)); } } for (int i = 0; i <= n; i++) { for (int j = 0; j < m; j++) { int v; cin >> v; edges[i][j].push_back(edge(pii(i, j+1), v)); edges[i][j+1].push_back(edge(pii(i, j), v)); expans_graph[hsh(i, j, 0)].push_back(pii(hsh(i, j+1, 1), v)); expans_graph[hsh(i, j, 3)].push_back(pii(hsh(i, j+1, 2), v)); expans_graph[hsh(i, j+1, 1)].push_back(pii(hsh(i, j, 0), v)); expans_graph[hsh(i, j+1, 2)].push_back(pii(hsh(i, j, 3), v)); } } dijkstra(); pruned[0][0] = 1; for (pii p: village_list) { prune(p); path_mask[p.first][p.second] |= 9; path_mask[p.first+1][p.second] |= 3; path_mask[p.first][p.second+1] |= 12; path_mask[p.first+1][p.second+1] |= 6; } // node numbering scheme: row, column index*4 + direction index. right-up, up-left, left-down, down-right for directions for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i == 0 && j == 0) continue; if (!(path_mask[i][j] & 1)) { expans_graph[hsh(i, j, 0)].push_back(pii(hsh(i, j, 3), 0)); expans_graph[hsh(i, j, 3)].push_back(pii(hsh(i, j, 0), 0)); } if (!(path_mask[i][j] & 2)) { expans_graph[hsh(i, j, 0)].push_back(pii(hsh(i, j, 1), 0)); expans_graph[hsh(i, j, 1)].push_back(pii(hsh(i, j, 0), 0)); } if (!(path_mask[i][j] & 4)) { expans_graph[hsh(i, j, 1)].push_back(pii(hsh(i, j, 2), 0)); expans_graph[hsh(i, j, 2)].push_back(pii(hsh(i, j, 1), 0)); } if (!(path_mask[i][j] & 8)) { expans_graph[hsh(i, j, 2)].push_back(pii(hsh(i, j, 3), 0)); expans_graph[hsh(i, j, 3)].push_back(pii(hsh(i, j, 2), 0)); } } } fill(dist2, dist2+4*MAXN*MAXN, inf); dijkstra2(); cout << dist2[hsh(0, 0, 2)] << "\n"; }

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

wall.cpp: In function 'int main()':
wall.cpp:114:8: warning: unused variable 'hsh1' [-Wunused-variable]
  114 |    int hsh1 = hsh(i, j, 3);
      |        ^~~~
wall.cpp:115:8: warning: unused variable 'hsh2' [-Wunused-variable]
  115 |    int hsh2 = hsh(i+1, j, 1);
      |        ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...