oj.uz

Submission #1016272

# Submission time Handle Problem Language Result Execution time Memory
1016272 2024-07-07T15:34:50 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=8;
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 199 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 28 ms 8792 KB Output is correct
2 Correct 27 ms 8796 KB Output is correct
3 Correct 17 ms 8796 KB Output is correct
4 Correct 138 ms 10112 KB Output is correct
5 Correct 126 ms 10112 KB Output is correct
6 Correct 161 ms 10108 KB Output is correct
7 Correct 163 ms 10112 KB Output is correct
8 Correct 165 ms 10108 KB Output is correct
9 Correct 127 ms 10108 KB Output is correct
10 Correct 128 ms 10108 KB Output is correct
11 Correct 156 ms 11516 KB Output is correct
12 Correct 169 ms 10112 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6735 ms 14116 KB Output is correct
2 Correct 7497 ms 14116 KB Output is correct
3 Correct 7531 ms 14080 KB Output is correct
4 Correct 7444 ms 14120 KB Output is correct
5 Correct 7000 ms 14116 KB Output is correct
6 Correct 20 ms 8796 KB Output is correct
7 Correct 17 ms 8916 KB Output is correct
8 Correct 16 ms 8796 KB Output is correct
9 Execution timed out 20014 ms 14116 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 209 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 6131 ms 14120 KB Output is correct
2 Correct 6617 ms 13860 KB Output is correct
3 Correct 6774 ms 14120 KB Output is correct
4 Correct 6368 ms 14120 KB Output is correct
5 Correct 7063 ms 14120 KB Output is correct
6 Runtime error 172 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 6568 ms 14116 KB Output is correct
2 Correct 6986 ms 14120 KB Output is correct
3 Correct 6846 ms 14120 KB Output is correct
4 Correct 6779 ms 14120 KB Output is correct
5 Correct 6754 ms 14136 KB Output is correct
6 Runtime error 187 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -