Submission #935077

#TimeUsernameProblemLanguageResultExecution timeMemory
935077antonWombats (IOI13_wombats)C++17
39 / 100
622 ms32760 KiB
#include "wombats.h" #include<bits/stdc++.h> using namespace std; #define pii pair<int, int> int tr[5000][200][3]; int delta[3][2] = {{0, 1}, {0, -1}, {1, 0}}; int dist[5000][200]; const int MAT_SZ= 20; struct Mat{ int dt[MAT_SZ][MAT_SZ]; Mat(){ for(int i = 0; i<MAT_SZ; i++){ for(int j = 0; j<MAT_SZ; j++){ dt[i][j] = 1e9; } } } }; int r, c; Mat e(){ Mat res; for(int i = 0; i<MAT_SZ; i++){ res.dt[i][i] = 0; } return res; } Mat compose(Mat& a, Mat& b){ Mat res= Mat(); for(int i = 0; i<c; i++){ for(int j= 0; j<c; j++){ for(int k = 0; k<c; k++){ res.dt[i][k] = min(res.dt[i][k], a.dt[i][j] + b.dt[j][k]); } } } return res; } Mat tr1[5000]; Mat global; vector<pair<pii, int>> gen_adj(pii pos){ vector<pair<pii, int>> res; for(int trid = 0; trid<3; trid++){ pii potential = {pos.first + delta[trid][0], pos.second + delta[trid][1]}; if(potential.first<r && potential.second>=0 && potential.second<c){ res.push_back({potential, tr[pos.first][pos.second][trid]}); } } return res; } int dijkstra(pii begin, pii dest){ for(int i = 0; i<r; i++){ for(int j = 0; j<c; j++){ dist[i][j] = 1e9; } } priority_queue<pair<int, pii>> pq; pq.push({0, begin}); dist[begin.first][begin.second] = 0; while(pq.size()>0){ auto cur = pq.top(); pq.pop(); pii pos= cur.second; int d = -cur.first; //cout<<pos.first<<" "<<pos.second<<" "<<d<<endl; if(d== dist[pos.first][pos.second]){ auto adj = gen_adj(pos); for(auto e: adj){ if(e.first.first<= dest.first && d + e.second< dist[e.first.first][e.first.second]){ dist[e.first.first][e.first.second]= d + e.second; pq.push({-d-e.second, e.first}); } } } } return dist[dest.first][dest.second]; } void find_global(){ Mat cur = e(); for(int i = 0; i<r-1; i++){ cur = compose(cur, tr1[i]); } global =cur; } void init(int R, int C, int H[5000][200], int V[5000][200]) { r= R; c= C; for(int p = 0; p<R; p++){ for(int q= 0; q<C-1; q++){ tr[p][q][0] = H[p][q]; tr[p][q+1][1] = H[p][q]; } if(p<R-1){ for(int q= 0; q<C; q++){ tr[p][q][2] = V[p][q]; } } } for(int p = 0; p<R-1; p++){ for(int q= 0; q<C; q++){ dijkstra({p, q}, {p+1, q}); for(int qt= 0; qt<C; qt++){ tr1[p].dt[q][qt] = dist[p+1][qt]; } } } find_global(); } void changeH(int P, int Q, int W) { tr[P][Q][0] = W; tr[P][Q+1][1] = W; for(int p = max(0, P-1); p<=min(P, r-2); p++){ for(int q= 0; q<c; q++){ dijkstra({p, q}, {p+1, q}); for(int qt= 0; qt<c; qt++){ tr1[p].dt[q][qt] = dist[p+1][qt]; } } } find_global(); } void changeV(int P, int Q, int W) { tr[P][Q][2] = W; for(int q= 0; q<c; q++){ dijkstra({P, q}, {P+1, q}); for(int qt= 0; qt<c; qt++){ tr1[P].dt[q][qt] = dist[P+1][qt]; } } find_global(); } int escape(int V1, int V2) { return global.dt[V1][V2]; }

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;
      |      ^~~
#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...