Submission #52007

#TimeUsernameProblemLanguageResultExecution timeMemory
52007radoslav11Wombats (IOI13_wombats)C++14
39 / 100
20068 ms41420 KiB
#include <bits/stdc++.h> #include "wombats.h" //#include "Lgrader.cpp" using namespace std; template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const int MAXN = 5002; const int MAXM = 202; const int B = 100; const int inf = (int)1e9; using matrix = array<array<int, MAXM>, MAXM>; int n, m; int H[MAXN + 42][MAXM + 42]; int V[MAXN + 42][MAXM + 42]; matrix tmp; matrix dist[B + 3]; bool in_queue[MAXM][B + 3]; matrix bfs_brute(int l, int r) { for(int ll = 0; ll < (r - l + 1); ll++) for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) dist[ll][i][j] = inf; for(int st = 0; st < m; st++) { for(int i = 0; i < m; i++) for(int ll = 0; ll < (r - l + 1); ll++) in_queue[i][ll] = false; queue<pair<int, int> > Q; Q.push({st, 0}); dist[0][st][st] = 0; in_queue[st][0] = true; while(!Q.empty()) { int pos = Q.front().first, ll = Q.front().second; Q.pop(), in_queue[pos][ll] = false; if(pos && chkmin(dist[ll][st][pos - 1], dist[ll][st][pos] + H[ll + l][pos - 1]) && !in_queue[pos - 1][ll]) Q.push({pos - 1, ll}), in_queue[pos - 1][ll] = true; if(pos < m - 1 && chkmin(dist[ll][st][pos + 1], dist[ll][st][pos] + H[ll + l][pos]) && !in_queue[pos + 1][ll]) Q.push({pos + 1, ll}), in_queue[pos + 1][ll] = true; if(ll + l < r && chkmin(dist[ll + 1][st][pos], dist[ll][st][pos] + V[ll + l][pos]) && !in_queue[pos][ll + 1]) Q.push({pos, ll + 1}), in_queue[pos][ll + 1] = true; } } return dist[r - l]; } int opt[MAXM][MAXN]; matrix merge(const matrix &f, const matrix &s) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) tmp[i][j] = inf; for(int j = 0; j < m; j++) for(int c = 0; c < m; c++) if(chkmin(tmp[0][j], f[0][c] + s[c][j])) opt[0][j] = c; for(int i = 1; i < m; i++) { opt[i][m] = m - 1; for(int j = m - 1; j >= 0; j--) for(int c = opt[i][j + 1]; c >= opt[i - 1][j]; c--) if(chkmin(tmp[i][j], f[i][c] + s[c][j])) opt[i][j] = c; } return tmp; } matrix tr[MAXN * 4 / B + 10]; void init(int l, int r, int idx) { if(r - l <= B) { tr[idx] = bfs_brute(l, r + 1); return; } int mid = (l + r) >> 1; init(l, mid, 2 * idx + 1); init(mid + 1, r, 2 * idx + 2); tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]); } void recalc(int p, int l, int r, int idx) { if(r - l <= B) { tr[idx] = bfs_brute(l, r + 1); return; } int mid = (l + r) >> 1; if(p <= mid) recalc(p, l, mid, 2 * idx + 1); else recalc(p, mid + 1, r, 2 * idx + 2); tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]); } void init(int R, int C, int H[5000][200], int V[5000][200]) { n = R, m = C; for(int i = 0; i < n; i++) for(int j = 0; j < m - 1; j++) ::H[i][j] = H[i][j]; for(int i = 0; i < n - 1; i++) for(int j = 0; j < m; j++) ::V[i][j] = V[i][j]; for(int i = 0; i < m - 1; i++) ::H[n][i] = inf; init(0, n - 1, 0); } void changeH(int P, int Q, int W) { H[P][Q] = W; recalc(P, 0, n - 1, 0); //init(0, n - 1, 0); } void changeV(int P, int Q, int W) { V[P][Q] = W; recalc(P, 0, n - 1, 0); //init(0, n - 1, 0); } int escape(int V1, int V2) { return tr[0][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]
  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...