Submission #943269

#TimeUsernameProblemLanguageResultExecution timeMemory
943269yhkhooPortals (BOI14_portals)C++17
0 / 100
11 ms3672 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define lb(vec, val) lower_bound((vec).begin(), (vec).end(), (val)) int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int r, c; cin >> r >> c; char m[r][c]; vector<vector<int>> cw(c), rw(r); int S, C; for(int i=0; i<c; i++){ cw[i].push_back(-1); } for(int i=0; i<r; i++){ rw[i].push_back(-1); for(int j=0; j<c; j++){ cin >> m[i][j]; if(m[i][j] == '#'){ rw[i].push_back(j); cw[j].push_back(i); } else if(m[i][j] == 'S'){ S = i*c+j; } else if(m[i][j] == 'C'){ C = i*c+j; } } rw[i].push_back(c); } for(int i=0; i<c; i++){ cw[i].push_back(r); } vector<vector<pii>> al(r*c); //i*c+j for(int i=0; i<r; i++){ for(int j=0; j<c; j++){ int nn = i*c+j; if(m[i][j] == '#') continue; auto w3 = lb(cw[j],i); auto w1 = w3-1; auto w2 = lb(rw[i],j); auto w4 = w2-1; int dw = /*min(min(i-*w1, *w3-i), min(j-*w4, *w2-j))*/ 1; //if(i-*w1 > 2){ al[nn].emplace_back((*w1+1)*c+j, dw); //} //if(*w3-i > 2){ al[nn].emplace_back((*w3-1)*c+j, dw); //} //if(j-*w4 > 2){ al[nn].emplace_back(i*c+(*w4+1), dw); //} //if(*w2-j > 2){ al[nn].emplace_back(i*c+(*w2-1), dw); //} } } int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; vector<bool> vi(r*c, 0); queue<int> q; vi[S] = 1; q.push(S); while(q.size()){ int cn = q.front(); q.pop(); for(int k=0; k<4; k++){ int cx = cn/c + dx[k]; int cy = cn%c + dy[k]; if(cx == -1 || cy == -1 || cx == r || cy == c) continue; if(m[cx][cy] == '#') continue; int knn = cx*c+cy; if(vi[knn]) continue; al[cn].emplace_back(knn, 1); al[knn].emplace_back(cn, 1); vi[knn] = true; q.push(knn); } } /*cout << '\n'; for(int i=0; i<al.size(); i++){ cout << i << ':'; for(auto j: al[i]){ cout << j.first << ' ' << j.second << ' ' << ' '; } cout << '\n'; }*/ priority_queue<pii, vector<pii>, greater<pii>> pq; fill(vi.begin(), vi.end(), false); vector<int> dst(r*c, 1e9); dst[S] = 0; pq.emplace(0, S); while(pq.size()){ auto[cd, cn] = pq.top(); pq.pop(); if(dst[cn] != cd) continue; if(vi[cn]) continue; for(auto [ccb, w] : al[cn]){ if(dst[ccb] <= cd+w) continue; dst[ccb] = cd+w; pq.emplace(dst[ccb], ccb); } vi[cn] = true; } cout << dst[C]; return 0; }

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:109:15: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |  cout << dst[C];
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...