Submission #155851

#TimeUsernameProblemLanguageResultExecution timeMemory
155851TAISA_Wombats (IOI13_wombats)C++14
55 / 100
10016 ms26040 KiB
#include "wombats.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<int, int>; const int INF = (1 << 30) - 1; const ll LINF = (1LL << 60) - 1LL; int type, h, w, sum1; struct edge { int y, x, cst; }; vector<edge> G[110][110]; int d[110][110], dp0[5001][2], dp1[5001][2]; int v[5000][200], hh[5000][200]; void recalc() { for (int i = 0; i <= h; i++) { dp0[i][0] = INF; dp0[i][1] = INF; dp1[i][0] = INF; dp1[i][1] = INF; } dp0[0][0] = 0; dp0[0][1] = hh[0][0]; dp1[0][1] = 0; dp1[0][0] = hh[0][0]; for (int i = 1; i < h; i++) { dp0[i][0] = min(dp0[i - 1][0] + v[i - 1][0], dp0[i - 1][1] + v[i - 1][1] + hh[i][0]); dp0[i][1] = min(dp0[i - 1][1] + v[i - 1][1], dp0[i - 1][0] + v[i - 1][0] + hh[i][0]); dp1[i][0] = min(dp1[i - 1][0] + v[i - 1][0], dp1[i - 1][1] + v[i - 1][1] + hh[i][0]); dp1[i][1] = min(dp1[i - 1][1] + v[i - 1][1], dp1[i - 1][0] + v[i - 1][0] + hh[i][0]); } } void init(int R, int C, int H[5000][200], int V[5000][200]) { h = R, w = C; sum1 = 0; for (int i = 0; i < h - 1; i++) { for (int j = 0; j < w; j++) { v[i][j] = V[i][j]; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w - 1; j++) { hh[i][j] = H[i][j]; } } if (w == 1) { type = 1; for (int i = 0; i < h - 1; i++) { sum1 += V[i][0]; } } else if (h <= 20 && w <= 20) { type = 2; } else if (h <= 100 && w <= 100) { type = 3; } else if (w == 2) { type = 4; } if (type == 2 || type == 3) { for (int i = 0; i < h; i++) { for (int j = 0; j < w - 1; j++) { G[i][j].push_back(edge{i, j + 1, H[i][j]}); G[i][j + 1].push_back(edge{i, j, H[i][j]}); } } for (int i = 0; i < h - 1; i++) { for (int j = 0; j < w; j++) { G[i][j].push_back(edge{i + 1, j, V[i][j]}); } } } else if (type == 4) { recalc(); } } void changeH(int P, int Q, int W) { if (type == 2 || type == 3) { vector<edge> to; for (auto &e : G[P][Q]) { if (e.y == P && e.x == Q + 1) { continue; } to.push_back(e); } to.push_back(edge{P, Q + 1, W}); G[P][Q] = to; to.clear(); for (auto &e : G[P][Q + 1]) { if (e.y == P && e.x == Q) { continue; } to.push_back(e); } to.push_back(edge{P, Q, W}); G[P][Q + 1] = to; } else if (type == 4) { hh[P][Q] = W; recalc(); } } void changeV(int P, int Q, int W) { if (type == 1) { sum1 -= v[P][Q]; sum1 += W; v[P][Q] = W; } else if (type == 2 || type == 3) { vector<edge> to; for (auto &e : G[P][Q]) { if (e.y == P + 1 && e.x == Q) { continue; } to.push_back(e); } to.push_back(edge{P + 1, Q, W}); G[P][Q] = to; } else if (type == 4) { v[P][Q] = W; recalc(); } } int escape(int V1, int V2) { if (type == 1) { return sum1; } else if (type == 2 || type == 3) { priority_queue<pair<int, P>, vector<pair<int, P>>, greater<pair<int, P>>> q; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { d[i][j] = INF; } } d[0][V1] = 0; q.push(make_pair(0, P(0, V1))); while (!q.empty()) { int ds = q.top().first, y = q.top().second.first, x = q.top().second.second; q.pop(); if (ds > d[y][x]) { continue; } for (auto &e : G[y][x]) { if (d[e.y][e.x] > d[y][x] + e.cst) { d[e.y][e.x] = d[y][x] + e.cst; q.push(make_pair(d[e.y][e.x], P(e.y, e.x))); } } } return d[h - 1][V2]; } else if (type == 4) { if (V1 == 0) { return dp0[h - 1][V2]; } else { return dp1[h - 1][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]
  int res;
      ^~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:162:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...