oj.uz

Submission #1016270

# Submission time Handle Problem Language Result Execution time Memory
1016270 2024-07-07T15:31:43 Z huutuan Wombats (IOI13_wombats) C++14
12 / 100
 20000 ms 177072 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;

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+9)/10);
   st.build(0, 0, st.n-1);
   for (int il=0, ir=9; il<R; il+=10, ir+=10){
      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/10]].data=cur;
   }
   st.build2(0, 0, st.n-1);
}

void changeH(int P, int Q, int W) {
   H[P][Q]=W;
   int il=P/10*10, ir=min(il+9, 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/10]].data=cur;
   st.update(0, 0, st.n-1, il/10);
}

void changeV(int P, int Q, int W) {
   V[P][Q]=W;
   int il=(P+1)/10*10, ir=min(il+9, 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/10]].data=cur;
   st.update(0, 0, st.n-1, il/10);
}

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 Execution timed out 20039 ms 173032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8796 KB Output is correct
2 Correct 14 ms 8792 KB Output is correct
3 Correct 13 ms 8796 KB Output is correct
4 Correct 119 ms 9404 KB Output is correct
5 Correct 106 ms 9404 KB Output is correct
6 Correct 109 ms 9404 KB Output is correct
7 Correct 118 ms 9404 KB Output is correct
8 Correct 114 ms 9404 KB Output is correct
9 Correct 135 ms 9404 KB Output is correct
10 Correct 120 ms 9404 KB Output is correct
11 Correct 157 ms 11384 KB Output is correct
12 Correct 122 ms 9400 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7105 ms 14120 KB Output is correct
2 Correct 7520 ms 14116 KB Output is correct
3 Correct 7406 ms 14120 KB Output is correct
4 Correct 7338 ms 14116 KB Output is correct
5 Correct 7670 ms 14372 KB Output is correct
6 Correct 14 ms 8796 KB Output is correct
7 Correct 14 ms 8860 KB Output is correct
8 Correct 14 ms 8712 KB Output is correct
9 Execution timed out 20085 ms 14112 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20029 ms 177072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6961 ms 14116 KB Output is correct
2 Correct 7639 ms 14120 KB Output is correct
3 Correct 7769 ms 14116 KB Output is correct
4 Correct 7818 ms 14120 KB Output is correct
5 Correct 8067 ms 14120 KB Output is correct
6 Execution timed out 20031 ms 176864 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7645 ms 14116 KB Output is correct
2 Correct 8042 ms 14116 KB Output is correct
3 Correct 7845 ms 14116 KB Output is correct
4 Correct 8415 ms 14120 KB Output is correct
5 Correct 8217 ms 14120 KB Output is correct
6 Execution timed out 20061 ms 176972 KB Time limit exceeded
7 Halted 0 ms 0 KB -