oj.uz

Submission #962317

# Submission time Handle Problem Language Result Execution time Memory
962317 2024-04-13T10:32:12 Z danikoynov Wombats (IOI13_wombats) C++14
100 / 100
 15710 ms 94672 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;

const int maxr = 5010, maxc = 210;
const int maxblock = sqrt(maxr) + 10;
void precalculate();
int h[maxr][maxc], v[maxr][maxc], dp[maxblock][maxc][maxc];
int r, c, block_size;

struct node
{
     int t[maxc][maxc];

     node()
     {
          for (int i = 0; i < maxc; i ++)
               for (int j = 0; j < maxc; j ++)
          {
               t[i][j] = 0;
          }
     }
};

const int inf = 2e9 + 10;

node tree[4 * maxblock];
int opt[maxc][maxc];
void divide(int &row, int &root, int &i, int left, int right, int optl, int optr)
{
     if (left > right)
          return;

     int mid = (left + right) / 2;
     int opt = -1;
     for (int k = optl; k <= optr; k ++)
     {
          int var = tree[root * 2].t[i][k] + tree[root * 2 + 1].t[k][mid] + v[row - 1][k];
          if (var < tree[root].t[i][mid])
          {
               opt = k;
               tree[root].t[i][mid] = var;
          }
     }

     divide(row, root, i, left, mid - 1, optl, opt);
     divide(row, root, i, mid + 1, right, opt, optr);
}
void unite(int root, int row)
{
     for (int i = 0; i < c; i ++)
     for (int j = 0; j < c; j ++)
     tree[root].t[i][j] = inf;

     int var;
     for (int i = 0; i < c; i ++)
     {
          divide(row, root, i, 0, c - 1, 0, c - 1);
          /**
          for (int j = 0; j < c; j ++)
          for (int k = 0; k < c; k ++)
          {
               var =tree[root * 2].t[i][k] + tree[root * 2 + 1].t[k][j] + v[row - 1][k];
               if (var < tree[root].t[i][j])
               {
                    tree[root].t[i][j] = var;
                    opt[i][j] = k;
               }
               //tree[root].t[i][j] = min(tree[root].t[i][j], );
          }*/
     }

     /**for (int i = 0; i < c; i ++)
     {
          for (int j = i + 1; j < c; j ++)
          {
               assert(opt[i][j] >= opt[i][j - 1]);
          }
     }*/

}

void get_leaf(int root, int bl)
{
     for (int i = 0; i < c; i ++)
          for (int j = 0; j < c; j ++)
          tree[root].t[i][j] = dp[bl][i][j];
}

void build(int root, int left, int right)
{
     if (left == right)
     {
          get_leaf(root, left);
          return;
     }

     int mid = (left + right) / 2;
     build(root * 2, left, mid);
     build(root * 2 + 1, mid + 1, right);

     unite(root, (mid + 1) * block_size);
}

void update(int root, int left, int right, int pivot)
{
     if (left == right)
     {
          get_leaf(root, left);
          return;
     }

     int mid = (left + right) / 2;
     if (pivot <= mid)
          update(root * 2, left, mid, pivot);
     else
          update(root * 2 + 1, mid + 1, right, pivot);

     unite(root, (mid + 1) * block_size);
}

int m;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    block_size = sqrt(R) + 1; /// maybe by 10 ???
    r = R;
    c = C;
    for (int i = 0; i < R - 1; i ++)
     for (int j = 0; j < C; j ++)
     v[i][j] = V[i][j];

    for (int i = 0; i < R; i ++)
     for (int j = 0; j < C - 1; j ++)
     h[i][j] = H[i][j];

     precalculate();
     m = (r - 1) / block_size;
     build(1, 0, m);
}


int fp[2][maxc];
void fix_row(int i)
{
     for (int j = 1; j < c; j ++)
     {
          fp[i & 1][j] = min(fp[i & 1][j], fp[i & 1][j - 1] + h[i][j - 1]);
     }
     for (int j = c - 2; j >= 0; j --)
     {
          fp[i & 1][j] = min(fp[i & 1][j], fp[i & 1][j + 1] + h[i][j]);
     }
}


void calc_block(int bl)
{

     int st = bl * block_size;
     int en = (bl + 1) * block_size - 1;

     en = min(en, r - 1);

     for (int d = 0; d < c; d ++)
     {
          for (int j = 0; j < c; j ++)
          {
               fp[0][j] = fp[1][j] = inf;
          }

          fp[st & 1][d] = 0;
          fix_row(st);

          for (int i = st + 1; i <= en; i ++)
          {
               for (int j = 0; j < c; j ++)
               {
                    fp[i & 1][j] = fp[(i - 1) & 1][j] + v[i - 1][j];
               }
               fix_row(i);
          }

          for (int j = 0; j < c; j ++)
          {
               dp[bl][d][j] = fp[en & 1][j];
          }
     }

}


void precalculate()
{
        for (int bl = 0; bl <= (r - 1) / block_size; bl ++)
     {

         /// cout << "calc block " << endl;
          calc_block(bl);
     }
     ///exit(0);
}

void changeH(int P, int Q, int W) {
    /* ... */
    h[P][Q] = W;
    calc_block(P / block_size);
    update(1, 0, m, P / block_size);
}

void changeV(int P, int Q, int W) {
    /* ... */
    v[P][Q] = W;
    calc_block(P / block_size);
    update(1, 0, m, P / block_size);
}


int arr[maxc], temp[maxc];
int escape(int V1, int V2)
{
     return tree[1].t[V1][V2];
     int v1 = V1, v2 = V2;
     for (int j = 0; j < c; j ++)
          arr[j] = dp[0][v1][j];

     for (int bl = 1; bl <= (r - 1) / block_size; bl ++)
     {
          int t = bl * block_size;
          for (int j = 0; j < c; j ++)
          {
               arr[j] = arr[j] + v[t - 1][j];
          }

          for (int j = 1; j < c; j ++)
          {
               arr[j] = min(arr[j], arr[j - 1] + h[t][j - 1]);
          }
          for (int j = c - 2; j >= 0; j --)
          {
               arr[j] = min(arr[j], arr[j + 1] + h[t][j]);
          }

          for (int j = 0; j < c; j ++)
               temp[j] = inf;

          for (int j = 0; j < c; j ++)
          {
               for (int d = 0; d < c; d ++)
                    temp[j] =min(temp[j], arr[d] + dp[bl][d][j]);
          }

          for (int j = 0; j < c; j ++)
               arr[j] = temp[j];
     }

     return arr[v2];
}

Compilation message

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 unite(int, int)':
wombats.cpp:56:10: warning: unused variable 'var' [-Wunused-variable]
   56 |      int var;
      |          ^~~
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:133:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  133 |     for (int i = 0; i < R; i ++)
      |     ^~~
wombats.cpp:137:6: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  137 |      precalculate();
      |      ^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 80584 KB Output is correct
2 Correct 14 ms 80732 KB Output is correct
3 Correct 67 ms 82016 KB Output is correct
4 Correct 13 ms 80472 KB Output is correct
5 Correct 11 ms 80476 KB Output is correct
6 Correct 8 ms 59740 KB Output is correct
7 Correct 8 ms 59740 KB Output is correct
8 Correct 8 ms 59740 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 59740 KB Output is correct
2 Correct 8 ms 59740 KB Output is correct
3 Correct 8 ms 59740 KB Output is correct
4 Correct 9 ms 63836 KB Output is correct
5 Correct 9 ms 63836 KB Output is correct
6 Correct 11 ms 63832 KB Output is correct
7 Correct 9 ms 63832 KB Output is correct
8 Correct 8 ms 63836 KB Output is correct
9 Correct 12 ms 63836 KB Output is correct
10 Correct 9 ms 64088 KB Output is correct
11 Correct 66 ms 65056 KB Output is correct
12 Correct 9 ms 63836 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 66180 KB Output is correct
2 Correct 195 ms 66140 KB Output is correct
3 Correct 199 ms 66172 KB Output is correct
4 Correct 209 ms 66164 KB Output is correct
5 Correct 211 ms 66164 KB Output is correct
6 Correct 9 ms 59740 KB Output is correct
7 Correct 7 ms 59924 KB Output is correct
8 Correct 8 ms 59932 KB Output is correct
9 Correct 947 ms 66168 KB Output is correct
10 Correct 10 ms 63836 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 85592 KB Output is correct
2 Correct 14 ms 85596 KB Output is correct
3 Correct 14 ms 85508 KB Output is correct
4 Correct 43 ms 86352 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 66140 KB Output is correct
2 Correct 219 ms 66164 KB Output is correct
3 Correct 223 ms 66128 KB Output is correct
4 Correct 199 ms 66168 KB Output is correct
5 Correct 216 ms 66168 KB Output is correct
6 Correct 32 ms 85512 KB Output is correct
7 Correct 14 ms 85596 KB Output is correct
8 Correct 14 ms 85596 KB Output is correct
9 Correct 64 ms 86392 KB Output is correct
10 Correct 11 ms 80472 KB Output is correct
11 Correct 13 ms 80480 KB Output is correct
12 Correct 65 ms 82200 KB Output is correct
13 Correct 15 ms 80472 KB Output is correct
14 Correct 12 ms 80476 KB Output is correct
15 Correct 8 ms 59740 KB Output is correct
16 Correct 8 ms 59740 KB Output is correct
17 Correct 8 ms 59740 KB Output is correct
18 Correct 15 ms 63832 KB Output is correct
19 Correct 10 ms 63836 KB Output is correct
20 Correct 9 ms 63836 KB Output is correct
21 Correct 10 ms 64060 KB Output is correct
22 Correct 9 ms 63836 KB Output is correct
23 Correct 9 ms 64020 KB Output is correct
24 Correct 8 ms 63836 KB Output is correct
25 Correct 64 ms 65016 KB Output is correct
26 Correct 10 ms 64088 KB Output is correct
27 Correct 965 ms 66164 KB Output is correct
28 Correct 3821 ms 86224 KB Output is correct
29 Correct 3582 ms 85460 KB Output is correct
30 Correct 3640 ms 85408 KB Output is correct
31 Correct 3956 ms 87076 KB Output is correct
32 Correct 12 ms 63836 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 66140 KB Output is correct
2 Correct 195 ms 66136 KB Output is correct
3 Correct 205 ms 66164 KB Output is correct
4 Correct 207 ms 66140 KB Output is correct
5 Correct 209 ms 66140 KB Output is correct
6 Correct 24 ms 85596 KB Output is correct
7 Correct 14 ms 85596 KB Output is correct
8 Correct 14 ms 85592 KB Output is correct
9 Correct 59 ms 86276 KB Output is correct
10 Correct 13 ms 80476 KB Output is correct
11 Correct 11 ms 80476 KB Output is correct
12 Correct 97 ms 82020 KB Output is correct
13 Correct 14 ms 80472 KB Output is correct
14 Correct 11 ms 80472 KB Output is correct
15 Correct 1782 ms 86104 KB Output is correct
16 Correct 15710 ms 87720 KB Output is correct
17 Correct 10 ms 59740 KB Output is correct
18 Correct 8 ms 59740 KB Output is correct
19 Correct 8 ms 59740 KB Output is correct
20 Correct 9 ms 63832 KB Output is correct
21 Correct 9 ms 63836 KB Output is correct
22 Correct 9 ms 63836 KB Output is correct
23 Correct 8 ms 63836 KB Output is correct
24 Correct 9 ms 64048 KB Output is correct
25 Correct 9 ms 63832 KB Output is correct
26 Correct 9 ms 64036 KB Output is correct
27 Correct 63 ms 66232 KB Output is correct
28 Correct 9 ms 64008 KB Output is correct
29 Correct 973 ms 66236 KB Output is correct
30 Correct 3995 ms 89824 KB Output is correct
31 Correct 15641 ms 94008 KB Output is correct
32 Correct 15702 ms 94200 KB Output is correct
33 Correct 3584 ms 88808 KB Output is correct
34 Correct 14253 ms 92852 KB Output is correct
35 Correct 3597 ms 88764 KB Output is correct
36 Correct 14504 ms 92616 KB Output is correct
37 Correct 3942 ms 91304 KB Output is correct
38 Correct 15679 ms 94672 KB Output is correct
39 Correct 18 ms 63836 KB Output is correct
40 Correct 14696 ms 92892 KB Output is correct