oj.uz

Submission #795570

# Submission time Handle Problem Language Result Execution time Memory
795570 2023-07-27T11:24:35 Z erray Wombats (IOI13_wombats) C++17
9 / 100
 5196 ms 170832 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "debug.h"
#else 
  #define debug(...) void(37)
#endif

#ifdef LOCAL
  const int mxC = 4;
#else 
  const int mxC = 200;
#endif
  
using node = array<array<int, mxC>, mxC>;
const int inf = int(1e9);
node emp;
node unite(node& l, node& r) {
  node res = emp;
  array<array<int, mxC>, mxC> opt{};
  for (int i = 0; i < mxC; ++i) {
    for (int j = mxC - 1; j >= 0; --j) {
      bool got = false;      
      for (int k = (i == 0 ? 0 : opt[i - 1][j]); k <= (j == mxC - 1 ? mxC - 1 : opt[i][j + 1]); ++k) {
        int add = l[i][k] + r[k][j];
        if (add < res[i][j]) {
          res[i][j] = add;
          opt[i][j] = k;
        }
          got = true;
      }
      assert(got);
    }
  }
  debug(opt);
  return res;
}

struct SegTree {
  vector<node> tree;
  int n;
  #define def int mid = (l + r) >> 1, rv = (v + (mid - l) * 2)
  void modify(int v, int l, int r, int p, node x) {
    debug(v, l, r);
    if (l + 1 == r) {
      tree[v] = x;
      return;  
    }
    def;
    if (p < mid) {
      modify(v + 1, l, mid, p, x);
    } else {
      modify(rv, mid, r, p, x);
    }
    tree[v] = unite(tree[v + 1], tree[rv]);
  }
  void modify(int p, node x) {
    modify(0, 0, n, p, x);
  }
  SegTree(int _n) : n(_n) {
    tree.resize(n * 2 - 1);    
  }
  SegTree() { }
};


SegTree st;
int BLOCK = 10;
int R, C;
vector<vector<int>> H;
vector<vector<int>> V;
void Upd(int x) {
  node res;
  bool first = true;
  for (int i = x * BLOCK; i < min(R, (x + 1) * BLOCK); ++i) {
    //debug(i);
    {
      node add = emp;
      for (int j = 0; j < C; ++j) {
        add[j][j] = 0;
      }
      for (int j = 0; j < C; ++j) {
        for (int k = j + 1; k < C; ++k) {
          add[j][k] = add[k][j] = add[j][k - 1] + H[i][k - 1];
        }       
      } 
      debug(add);
      res = (first ? add : unite(res, add));
      first = false;
    }
    debug(res);
    if (i < R - 1) {
      node add = emp;
      for (int j = 0; j < C; ++j) {
        add[j][j] = V[i][j];
      }
      debug(add);
      res = unite(res, add);
    }
    debug(i, res);
  }
  st.modify(x, res);
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
  for (int i = 0; i < mxC; ++i) {
    for (int j = 0; j < mxC; ++j) {
      emp[i][j] = inf;
    }
  }
  swap(R, _R);
  swap(C, _C);
  H.resize(R, vector<int>(C - 1));
  V.resize(R - 1, vector<int>(C));
  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < C - 1; ++j) {
      H[i][j] = _H[i][j];
    }
  }
  for (int i = 0; i < R - 1; ++i) {
    for (int j = 0; j < C; ++j) {
      V[i][j] = _V[i][j];
    }
  }
  debug(H, V);
  st = SegTree((R + BLOCK - 1) / BLOCK);
  debug(st.n);
  for (int i = 0; i * BLOCK < R; ++i) {
    Upd(i);
  }
  debug("init end");
}

void changeH(int P, int Q, int W) {
  H[P][Q] = W;
  Upd(P / BLOCK);
}

void changeV(int P, int Q, int W) {
  V[P][Q] = W;
  Upd(P / BLOCK);
}                    

int escape(int V1, int V2) {
  return st.tree[0][V1][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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5196 ms 166656 KB Output is correct
2 Correct 5146 ms 166688 KB Output is correct
3 Correct 5062 ms 169564 KB Output is correct
4 Correct 5065 ms 166580 KB Output is correct
5 Correct 5042 ms 166660 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 2 ms 2516 KB Output is correct
8 Correct 2 ms 2388 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 2 ms 2488 KB Output is correct
3 Correct 2 ms 2388 KB Output is correct
4 Incorrect 8 ms 2772 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 432 ms 6884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5121 ms 170832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 452 ms 6880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 455 ms 6980 KB Output isn't correct
2 Halted 0 ms 0 KB -