oj.uz

답안 #1016257

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016257 2024-07-07T15:04:49 Z huutuan 웜뱃 (IOI13_wombats) C++14
28 / 100
 18158 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;

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);
   st.build(0, 0, st.n-1);
   for (int i=0; i<R; ++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];
            st.t[st.id[i]].data[j][k]=sum+(i?V[i-1][j]:0);
            st.t[st.id[i]].data[k][j]=sum+(i?V[i-1][k]:0);
         }
      }
   }
   st.build2(0, 0, st.n-1);
}

void changeH(int P, int Q, int W) {
   H[P][Q]=W;
   int i=P;
   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];
         st.t[st.id[i]].data[j][k]=sum+(i?V[i-1][j]:0);
         st.t[st.id[i]].data[k][j]=sum+(i?V[i-1][k]:0);
      }
   }
   st.update(0, 0, st.n-1, i);
}

void changeV(int P, int Q, int W) {
   V[P][Q]=W;
   int i=P+1;
   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];
         st.t[st.id[i]].data[j][k]=sum+(i?V[i-1][j]:0);
         st.t[st.id[i]].data[k][j]=sum+(i?V[i-1][k]:0);
      }
   }
   st.update(0, 0, st.n-1, i);
}

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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 161 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9148 KB Output is correct
2 Correct 10 ms 9148 KB Output is correct
3 Correct 9 ms 9148 KB Output is correct
4 Correct 126 ms 18528 KB Output is correct
5 Correct 121 ms 18524 KB Output is correct
6 Correct 115 ms 18524 KB Output is correct
7 Correct 125 ms 18524 KB Output is correct
8 Correct 108 ms 18528 KB Output is correct
9 Correct 107 ms 18524 KB Output is correct
10 Correct 128 ms 18524 KB Output is correct
11 Correct 168 ms 18524 KB Output is correct
12 Correct 120 ms 18528 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3993 ms 48832 KB Output is correct
2 Correct 4249 ms 48820 KB Output is correct
3 Correct 4013 ms 48820 KB Output is correct
4 Correct 3889 ms 48824 KB Output is correct
5 Correct 3985 ms 48868 KB Output is correct
6 Correct 10 ms 9144 KB Output is correct
7 Correct 10 ms 9400 KB Output is correct
8 Correct 10 ms 9148 KB Output is correct
9 Correct 18158 ms 48904 KB Output is correct
10 Correct 38 ms 9856 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 186 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4130 ms 48820 KB Output is correct
2 Correct 4167 ms 50876 KB Output is correct
3 Correct 4127 ms 50720 KB Output is correct
4 Correct 4111 ms 50880 KB Output is correct
5 Correct 4128 ms 50872 KB Output is correct
6 Runtime error 180 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4070 ms 50852 KB Output is correct
2 Correct 4168 ms 50868 KB Output is correct
3 Correct 4077 ms 50848 KB Output is correct
4 Correct 3993 ms 50876 KB Output is correct
5 Correct 3987 ms 50732 KB Output is correct
6 Runtime error 186 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -