Submission #1068055

#TimeUsernameProblemLanguageResultExecution timeMemory
1068055kunzaZa183Wombats (IOI13_wombats)C++17
55 / 100
20104 ms24156 KiB
#pragma GCC optimize("O3") #include "wombats.h" #include <bits/stdc++.h> #include <utility> using namespace std; struct qry{ pair<int,int> pos; int w; bool operator<(qry x) const{ return w > x.w; } }; int hori[5000][200],verti[5000][200]; int dp[5000][200],r,c; int ans[200][200]; bitset<200> alrdid; const int big = 1e9+7; void dij(int a,int b,int in){ priority_queue<qry> pq; for(int i = 0; i < r; i++) for(int j = 0; j< c;j++) dp[i][j] = big; qry tmp; tmp.pos = {a,b}; tmp.w = 0; pq.push(tmp); while(!pq.empty()) { qry x = pq.top(); pq.pop(); if(dp[x.pos.first][x.pos.second] == big) { dp[x.pos.first][x.pos.second] = x.w; qry sth; if(x.pos.second!=0) { sth.pos = {x.pos.first,x.pos.second - 1}; sth.w = hori[sth.pos.first][sth.pos.second] + x.w; pq.push(sth); } if(x.pos.second != c - 1) { sth.pos = {x.pos.first, x.pos.second + 1}; sth.w = hori[x.pos.first][x.pos.second] + x.w; pq.push(sth); } if(x.pos.first != 0) { sth.pos = {x.pos.first - 1,x.pos.second}; sth.w = verti[sth.pos.first][sth.pos.second] + x.w; pq.push(sth); } } } for(int i = 0; i < c;i++) ans[in][i] = dp[0][i]; } void init(int R, int C, int H[5000][200], int V[5000][200]) { r = R, c= C; for(int i =0; i < R;i++) for(int j = 0; j < C;j++) hori[i][j] = H[i][j], verti[i][j] = V[i][j]; alrdid.reset(); } void changeH(int P, int Q, int W) { hori[P][Q] = W; alrdid.reset(); } void changeV(int P, int Q, int W) { verti[P][Q] = W; alrdid.reset(); } int escape(int V1, int V2) { if(!alrdid[V2]) dij(r-1,V2,V2); alrdid[V2] = 1; return ans[V2][V1]; }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'void dij(int, int, int)':
wombats.cpp:26:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   26 |   for(int i = 0; i < r; i++)
      |   ^~~
wombats.cpp:30:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   30 |     qry tmp;
      |     ^~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...