Submission #1016547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016547		huutuan	Wombats (IOI13_wombats)	C++14	100 / 100	4304 ms	186832 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24