oj.uz

Submission #1016273

# Submission time Handle Problem Language Result Execution time Memory
1016273 2024-07-07T15:36:24 Z huutuan Wombats (IOI13_wombats) C++14
76 / 100
 10396 ms 141752 KB 
#include "wombats.h"

#include <bits/stdc++.h>

using namespace std;

const int inf=1e9;

struct Matrix{
   int data[100][100];
   Matrix (int x=0){
      for (int i=0; i<100; ++i) for (int j=0; j<100; ++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<100; ++i){
         for (int k=0; k<100; ++k){
            for (int j=0; j<100; ++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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10232 ms 92636 KB Output is correct
2 Correct 9694 ms 92520 KB Output is correct
3 Correct 9959 ms 92780 KB Output is correct
4 Correct 9939 ms 92520 KB Output is correct
5 Correct 9604 ms 92480 KB Output is correct
6 Correct 5 ms 8280 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 7 ms 8412 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 18 ms 8796 KB Output is correct
5 Correct 20 ms 8796 KB Output is correct
6 Correct 19 ms 8796 KB Output is correct
7 Correct 18 ms 8796 KB Output is correct
8 Correct 17 ms 8796 KB Output is correct
9 Correct 16 ms 8796 KB Output is correct
10 Correct 19 ms 8796 KB Output is correct
11 Correct 60 ms 11024 KB Output is correct
12 Correct 20 ms 8792 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 776 ms 9856 KB Output is correct
2 Correct 881 ms 9852 KB Output is correct
3 Correct 843 ms 9856 KB Output is correct
4 Correct 846 ms 9852 KB Output is correct
5 Correct 872 ms 9852 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 5 ms 8436 KB Output is correct
9 Correct 4229 ms 9856 KB Output is correct
10 Correct 10 ms 8284 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9940 ms 96612 KB Output is correct
2 Correct 9317 ms 96612 KB Output is correct
3 Correct 9471 ms 96572 KB Output is correct
4 Correct 9781 ms 96580 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 9852 KB Output is correct
2 Correct 909 ms 9856 KB Output is correct
3 Correct 822 ms 9856 KB Output is correct
4 Correct 891 ms 9852 KB Output is correct
5 Correct 954 ms 9856 KB Output is correct
6 Correct 9723 ms 96568 KB Output is correct
7 Correct 10191 ms 96640 KB Output is correct
8 Correct 9836 ms 96572 KB Output is correct
9 Correct 9352 ms 96612 KB Output is correct
10 Correct 9597 ms 92516 KB Output is correct
11 Correct 9431 ms 92480 KB Output is correct
12 Correct 9466 ms 92540 KB Output is correct
13 Correct 9661 ms 92484 KB Output is correct
14 Correct 9317 ms 92644 KB Output is correct
15 Correct 5 ms 8284 KB Output is correct
16 Correct 5 ms 8440 KB Output is correct
17 Correct 5 ms 8284 KB Output is correct
18 Correct 20 ms 8792 KB Output is correct
19 Correct 20 ms 8796 KB Output is correct
20 Correct 20 ms 8796 KB Output is correct
21 Correct 20 ms 8796 KB Output is correct
22 Correct 20 ms 8680 KB Output is correct
23 Correct 20 ms 8796 KB Output is correct
24 Correct 20 ms 8796 KB Output is correct
25 Correct 59 ms 10932 KB Output is correct
26 Correct 21 ms 8796 KB Output is correct
27 Correct 4277 ms 9856 KB Output is correct
28 Correct 10396 ms 99960 KB Output is correct
29 Correct 9250 ms 58784 KB Output is correct
30 Correct 8619 ms 98664 KB Output is correct
31 Correct 9847 ms 99444 KB Output is correct
32 Correct 11 ms 8280 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 9856 KB Output is correct
2 Correct 908 ms 9852 KB Output is correct
3 Correct 938 ms 9856 KB Output is correct
4 Correct 882 ms 9856 KB Output is correct
5 Correct 916 ms 9856 KB Output is correct
6 Correct 9585 ms 96580 KB Output is correct
7 Correct 9592 ms 96832 KB Output is correct
8 Correct 9882 ms 96620 KB Output is correct
9 Correct 10002 ms 96588 KB Output is correct
10 Correct 9928 ms 92760 KB Output is correct
11 Correct 9881 ms 92800 KB Output is correct
12 Correct 9888 ms 92964 KB Output is correct
13 Correct 9423 ms 92804 KB Output is correct
14 Correct 9615 ms 92764 KB Output is correct
15 Runtime error 3837 ms 141752 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -