oj.uz

Submission #1016547

# Submission time Handle Problem Language Result Execution time Memory
1016547 2024-07-08T07:58:44 Z huutuan Wombats (IOI13_wombats) C++14
100 / 100
 4304 ms 186832 KB 
#include "wombats.h"

#include <bits/stdc++.h>

using namespace std;

const int inf=1e9;

int C;

struct Matrix{
   int data[200][200];
   Matrix (int x=0){
      for (int i=0; i<C; ++i) for (int j=0; j<C; ++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, opt;
      for (int i=0; i<C; ++i){
         ans[i][i]=-1;
         for (int j=0; j<C; ++j){
            if (ans[i][i]==-1 || ans[i][i]>min(inf, data[i][j]+a[j][i])){
               ans[i][i]=min(inf, data[i][j]+a[j][i]);
               opt[i][i]=j;
            }
         }
      }
      for (int d=1; d<C; ++d){
         for (int i=0, j=d; j<C; ++i, ++j){
            ans[i][j]=-1;
            for (int k=opt[i][j-1]; k<=opt[i+1][j]; ++k){
               if (ans[i][j]==-1 || ans[i][j]>min(inf, data[i][k]+a[k][j])){
                  ans[i][j]=min(inf, data[i][k]+a[k][j]);
                  opt[i][j]=k;
               }
            }
         }
         for (int i=d, j=0; i<C; ++i, ++j){
            ans[i][j]=-1;
            for (int k=opt[i-1][j]; k<=opt[i][j+1]; ++k){
               if (ans[i][j]==-1 || ans[i][j]>min(inf, data[i][k]+a[k][j])){
                  ans[i][j]=min(inf, data[i][k]+a[k][j]);
                  opt[i][j]=k;
               }
            }
         }
      }
      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=10;
int R, H[5000][200], V[5000][200];

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 172 ms 169748 KB Output is correct
2 Correct 162 ms 170888 KB Output is correct
3 Correct 200 ms 172560 KB Output is correct
4 Correct 170 ms 172832 KB Output is correct
5 Correct 155 ms 170608 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 3 ms 11428 KB Output is correct
5 Correct 3 ms 11428 KB Output is correct
6 Correct 3 ms 11424 KB Output is correct
7 Correct 3 ms 11448 KB Output is correct
8 Correct 3 ms 11332 KB Output is correct
9 Correct 3 ms 11428 KB Output is correct
10 Correct 4 ms 11292 KB Output is correct
11 Correct 41 ms 13600 KB Output is correct
12 Correct 3 ms 11424 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 16852 KB Output is correct
2 Correct 111 ms 16592 KB Output is correct
3 Correct 132 ms 17364 KB Output is correct
4 Correct 124 ms 16852 KB Output is correct
5 Correct 125 ms 16852 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 416 ms 16596 KB Output is correct
10 Correct 3 ms 11096 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 174908 KB Output is correct
2 Correct 156 ms 175884 KB Output is correct
3 Correct 180 ms 174032 KB Output is correct
4 Correct 180 ms 174632 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 16592 KB Output is correct
2 Correct 85 ms 16592 KB Output is correct
3 Correct 107 ms 16336 KB Output is correct
4 Correct 107 ms 16592 KB Output is correct
5 Correct 113 ms 16336 KB Output is correct
6 Correct 160 ms 175596 KB Output is correct
7 Correct 175 ms 177080 KB Output is correct
8 Correct 157 ms 173496 KB Output is correct
9 Correct 166 ms 177152 KB Output is correct
10 Correct 154 ms 173332 KB Output is correct
11 Correct 145 ms 169784 KB Output is correct
12 Correct 199 ms 172608 KB Output is correct
13 Correct 160 ms 170552 KB Output is correct
14 Correct 152 ms 172244 KB Output is correct
15 Correct 3 ms 9048 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 3 ms 11296 KB Output is correct
19 Correct 3 ms 11428 KB Output is correct
20 Correct 3 ms 11428 KB Output is correct
21 Correct 3 ms 11428 KB Output is correct
22 Correct 3 ms 11428 KB Output is correct
23 Correct 3 ms 11428 KB Output is correct
24 Correct 3 ms 11428 KB Output is correct
25 Correct 45 ms 13568 KB Output is correct
26 Correct 3 ms 11424 KB Output is correct
27 Correct 375 ms 16084 KB Output is correct
28 Correct 968 ms 180952 KB Output is correct
29 Correct 1164 ms 180056 KB Output is correct
30 Correct 1166 ms 178980 KB Output is correct
31 Correct 1075 ms 180628 KB Output is correct
32 Correct 3 ms 11096 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 17620 KB Output is correct
2 Correct 95 ms 17104 KB Output is correct
3 Correct 123 ms 16848 KB Output is correct
4 Correct 110 ms 17104 KB Output is correct
5 Correct 115 ms 16592 KB Output is correct
6 Correct 160 ms 176148 KB Output is correct
7 Correct 171 ms 173616 KB Output is correct
8 Correct 168 ms 177080 KB Output is correct
9 Correct 191 ms 174780 KB Output is correct
10 Correct 168 ms 173704 KB Output is correct
11 Correct 169 ms 170740 KB Output is correct
12 Correct 187 ms 172620 KB Output is correct
13 Correct 189 ms 170924 KB Output is correct
14 Correct 168 ms 169820 KB Output is correct
15 Correct 1527 ms 186832 KB Output is correct
16 Correct 4304 ms 185036 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct
18 Correct 2 ms 9052 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 3 ms 11424 KB Output is correct
21 Correct 3 ms 11428 KB Output is correct
22 Correct 3 ms 11264 KB Output is correct
23 Correct 3 ms 11428 KB Output is correct
24 Correct 3 ms 11428 KB Output is correct
25 Correct 3 ms 11292 KB Output is correct
26 Correct 4 ms 11428 KB Output is correct
27 Correct 41 ms 13724 KB Output is correct
28 Correct 3 ms 11424 KB Output is correct
29 Correct 399 ms 16084 KB Output is correct
30 Correct 1006 ms 180004 KB Output is correct
31 Correct 3424 ms 184016 KB Output is correct
32 Correct 3508 ms 183996 KB Output is correct
33 Correct 1164 ms 177652 KB Output is correct
34 Correct 4045 ms 184012 KB Output is correct
35 Correct 1138 ms 180228 KB Output is correct
36 Correct 3826 ms 183980 KB Output is correct
37 Correct 974 ms 179208 KB Output is correct
38 Correct 3471 ms 182984 KB Output is correct
39 Correct 3 ms 11096 KB Output is correct
40 Correct 4003 ms 183660 KB Output is correct