oj.uz

Submission #1016271

# Submission time Handle Problem Language Result Execution time Memory
1016271 2024-07-07T15:33:49 Z huutuan Wombats (IOI13_wombats) C++14
12 / 100
 20000 ms 262144 KB 
#include "wombats.h"

#include <bits/stdc++.h>

using namespace std;

const int inf=1e9;

struct Matrix{
   int data[200][200];
   Matrix (int x=0){
      for (int i=0; i<200; ++i) for (int j=0; j<200; ++j) data[i][j]=x && i==j?0:inf;
   }
   auto & operator[](int x){ return data[x]; }
   const auto & operator[](int x) const { return data[x]; }
   Matrix operator*(const Matrix &a){
      Matrix ans;
      for (int i=0; i<200; ++i){
         for (int k=0; k<200; ++k){
            for (int j=0; j<200; ++j){
               ans[i][j]=min(ans[i][j], data[i][k]+a[k][j]);
            }
         }
      }
      return ans;
   }
};

struct Node{
   Matrix data;
   int tl, tr;
   Node (){
      tl=tr=-1;
   }
};

struct SegmentTree{
   int n;
   vector<int> id;
   vector<Node> t;
   SegmentTree(){
      t.emplace_back();
   }
   void init(int _n){
      n=_n;
      id.assign(n, 0);
   }
   void build(int k, int l, int r){
      if (l==r){
         id[l]=k;
         return;
      }
      int mid=(l+r)>>1;
      t[k].tl=t.size();
      t.emplace_back();
      t[k].tr=t.size();
      t.emplace_back();
      build(t[k].tl, l, mid);
      build(t[k].tr, mid+1, r);
   }
   void build2(int k, int l, int r){
      if (l==r) return;
      int mid=(l+r)>>1;
      build2(t[k].tl, l, mid);
      build2(t[k].tr, mid+1, r);
      t[k].data=t[t[k].tl].data*t[t[k].tr].data;
   }
   void update(int k, int l, int r, int pos){
      if (l==r) return;
      int mid=(l+r)>>1;
      if (pos<=mid) update(t[k].tl, l, mid, pos);
      else update(t[k].tr, mid+1, r, pos);
      t[k].data=t[t[k].tl].data*t[t[k].tr].data;
   }
} st;

const int SZ=6;
int R, C, H[5000][200], V[5000][200];

void solve(){
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
   R=_R, C=_C;
   memcpy(H, _H, sizeof H);
   memcpy(V, _V, sizeof V);
   st.init((R+SZ-1)/SZ);
   st.build(0, 0, st.n-1);
   for (int il=0, ir=SZ-1; il<R; il+=SZ, ir+=SZ){
      ir=min(ir, R-1);
      Matrix cur(1), nxt;
      for (int i=il; i<=ir; ++i){
         for (int j=0; j<C; ++j){
            int sum=0;
            for (int k=j; k<C; ++k){
               if (k!=j) sum+=H[i][k-1];
               nxt[j][k]=sum+(i?V[i-1][j]:0);
               nxt[k][j]=sum+(i?V[i-1][k]:0);
            }
         }
         cur=cur*nxt;
      }
      st.t[st.id[il/SZ]].data=cur;
   }
   st.build2(0, 0, st.n-1);
}

void changeH(int P, int Q, int W) {
   H[P][Q]=W;
   int il=P/SZ*SZ, ir=min(il+SZ-1, R-1);
   Matrix cur(1), nxt;
   for (int i=il; i<=ir; ++i){
      for (int j=0; j<C; ++j){
         int sum=0;
         for (int k=j; k<C; ++k){
            if (k!=j) sum+=H[i][k-1];
            nxt[j][k]=sum+(i?V[i-1][j]:0);
            nxt[k][j]=sum+(i?V[i-1][k]:0);
         }
      }
      cur=cur*nxt;
   }
   st.t[st.id[il/SZ]].data=cur;
   st.update(0, 0, st.n-1, il/SZ);
}

void changeV(int P, int Q, int W) {
   V[P][Q]=W;
   int il=(P+1)/SZ*SZ, ir=min(il+SZ-1, R-1);
   Matrix cur(1), nxt;
   for (int i=il; i<=ir; ++i){
      for (int j=0; j<C; ++j){
         int sum=0;
         for (int k=j; k<C; ++k){
            if (k!=j) sum+=H[i][k-1];
            nxt[j][k]=sum+(i?V[i-1][j]:0);
            nxt[k][j]=sum+(i?V[i-1][k]:0);
         }
      }
      cur=cur*nxt;
   }
   st.t[st.id[il/SZ]].data=cur;
   st.update(0, 0, st.n-1, il/SZ);
}

int escape(int V1, int V2) {
   return st.t[0].data[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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 174 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8920 KB Output is correct
2 Correct 18 ms 8796 KB Output is correct
3 Correct 15 ms 8796 KB Output is correct
4 Correct 132 ms 10108 KB Output is correct
5 Correct 139 ms 10112 KB Output is correct
6 Correct 138 ms 10108 KB Output is correct
7 Correct 131 ms 10108 KB Output is correct
8 Correct 126 ms 10108 KB Output is correct
9 Correct 126 ms 10108 KB Output is correct
10 Correct 132 ms 10120 KB Output is correct
11 Correct 173 ms 12184 KB Output is correct
12 Correct 134 ms 10112 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5888 ms 19040 KB Output is correct
2 Correct 6330 ms 19036 KB Output is correct
3 Correct 6033 ms 19040 KB Output is correct
4 Correct 6045 ms 19176 KB Output is correct
5 Correct 6333 ms 19040 KB Output is correct
6 Correct 15 ms 8796 KB Output is correct
7 Correct 23 ms 8796 KB Output is correct
8 Correct 30 ms 8900 KB Output is correct
9 Execution timed out 20029 ms 19036 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 212 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6087 ms 19040 KB Output is correct
2 Correct 6694 ms 19040 KB Output is correct
3 Correct 6479 ms 19036 KB Output is correct
4 Correct 6298 ms 19040 KB Output is correct
5 Correct 6609 ms 19032 KB Output is correct
6 Runtime error 191 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6070 ms 19036 KB Output is correct
2 Correct 6164 ms 19036 KB Output is correct
3 Correct 6281 ms 18968 KB Output is correct
4 Correct 5932 ms 19036 KB Output is correct
5 Correct 6025 ms 19040 KB Output is correct
6 Runtime error 198 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -