oj.uz

Submission #593950

# Submission time Handle Problem Language Result Execution time Memory
593950 2022-07-11T17:58:56 Z jeroenodb Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 27184 KB 
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
#include "wombats.h"
void cmin(int& a, int b) {a=min(a,b);}
const int N = 200, K = 200, oo = 1e9;
static int HH[5000][N], VV[5000][N],R,C;

typedef array<array<int,N>,N> node;
const node identity() {
    node res = {};
    for(int i=0;i<N;++i) {
        for(int j=0;j<N;++j) res[i][j]=oo;
        res[i][i]=0;
    }
    return res;
}
node res;
void merge(const node& n1, const node& n2, int l, int r, int a, int b, int c, int d) {
    if(c==d or l==r) return;
    if(r-l<8 or d-c<8) {
        for(int i=l;i<r;++i) {
            for(int j=a;j<b;++j) {
                for(int k=c;k<d;++k) {
                    cmin(res[i][k],n1[i][j]+n2[j][k]);
                }
            }
        }
        return;
    }
    int m1 = (l+r)/2, m2 = (c+d)/2;
    pi opt = {n1[m1][a]+n2[a][m2],a};
    for(int j = a+1;j<b;++j) {
        opt = min(opt, {n1[m1][j]+n2[j][m2],j});
    }
    int pos = opt.second;
    merge(n1,n2,l,m1,a,pos+1,c,m2);
    merge(n1,n2,m1,r,pos,b,m2,d);
    merge(n1,n2,l,m1,a,b,m2,d);
    merge(n1,n2,m1,r,a,b,c,m2);
}

struct segtree {
    vector<node> nds;
    int ptwo;
    segtree(){}
    segtree(int n) {
        ptwo=1;
        while(ptwo<n) ptwo*=2;
        nds.assign(ptwo*2,identity());
    }
    node& operator[](int i) {
        return nds[i+ptwo];
    }
    void update(int b) {
        for(b = (b+ptwo)/2;b>=1;b/=2) {
            for(int i=0;i<N;++i) fill(all(res[i]),oo);
            merge(nds[b*2],nds[b*2+1],0,C,0,C,0,C);
            nds[b]=res;
        }
    }
    int query(int A, int B) {
        return nds[1][A][B];
    }
} seg;

void recalculate(int b) { // recalculates a block
    int l = b*K, r = min(R,(b+1)*K);
    int ans[N] = {};
    for(int s=0;s<C;++s) {
        
        fill(ans,ans+N,oo);
        ans[s] = 0;
        for(int i=l;i<r;++i) {
            for(int j=0;j<C-1;++j) {
                cmin(ans[j+1],ans[j]+HH[i][j]);
            }
            for(int j=C-1;j>=1;--j) {
                cmin(ans[j-1],ans[j]+HH[i][j-1]);
            }
            if(i!=R-1) for(int j=0;j<C;++j) ans[j]+=VV[i][j];
        }
        copy(ans,ans+N,seg[b][s].begin());
    }
    seg.update(b);
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
    ::R=R,::C=C;
    for(int i=0;i<R;++i) {
        copy(H[i],H[i]+C,HH[i]);
        copy(V[i],V[i]+C,VV[i]);
    }
    int SEGSIZE = (R+K-1)/K;
    seg = segtree(SEGSIZE);
    for(int i=0;i*K<R;++i) recalculate(i);
}




void changeH(int P, int Q, int W) {
    HH[P][Q]=W;
    int B = P/K;
    recalculate(B);
}

void changeV(int P, int Q, int W) {
    VV[P][Q]=W;
    int B = P/K;
    recalculate(B);
}

int escape(int V1, int V2) {
    return seg.query(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 49 ms 22356 KB Output is correct
2 Correct 46 ms 22312 KB Output is correct
3 Correct 135 ms 23920 KB Output is correct
4 Correct 52 ms 22356 KB Output is correct
5 Correct 43 ms 22400 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 67 ms 1832 KB Output is correct
12 Correct 1 ms 852 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1138 ms 1112 KB Output is correct
2 Correct 1145 ms 1108 KB Output is correct
3 Correct 1184 ms 1108 KB Output is correct
4 Correct 1221 ms 1108 KB Output is correct
5 Correct 1187 ms 1108 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 5855 ms 1108 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 26196 KB Output is correct
2 Correct 60 ms 26288 KB Output is correct
3 Correct 72 ms 26292 KB Output is correct
4 Correct 103 ms 27184 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1217 ms 1108 KB Output is correct
2 Correct 1150 ms 1108 KB Output is correct
3 Correct 1214 ms 1108 KB Output is correct
4 Correct 1204 ms 1108 KB Output is correct
5 Correct 1206 ms 1108 KB Output is correct
6 Correct 54 ms 26284 KB Output is correct
7 Correct 66 ms 26288 KB Output is correct
8 Correct 63 ms 26208 KB Output is correct
9 Correct 90 ms 27064 KB Output is correct
10 Correct 46 ms 22396 KB Output is correct
11 Correct 49 ms 22348 KB Output is correct
12 Correct 109 ms 23880 KB Output is correct
13 Correct 47 ms 22356 KB Output is correct
14 Correct 62 ms 22356 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 1 ms 852 KB Output is correct
23 Correct 1 ms 852 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 71 ms 1744 KB Output is correct
26 Correct 2 ms 852 KB Output is correct
27 Correct 5941 ms 1124 KB Output is correct
28 Execution timed out 20094 ms 26576 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1190 ms 1108 KB Output is correct
2 Correct 1144 ms 1108 KB Output is correct
3 Correct 1163 ms 1108 KB Output is correct
4 Correct 1182 ms 1108 KB Output is correct
5 Correct 1158 ms 1108 KB Output is correct
6 Correct 66 ms 26280 KB Output is correct
7 Correct 56 ms 26304 KB Output is correct
8 Correct 68 ms 26280 KB Output is correct
9 Correct 95 ms 27032 KB Output is correct
10 Correct 52 ms 22356 KB Output is correct
11 Correct 47 ms 22280 KB Output is correct
12 Correct 137 ms 24040 KB Output is correct
13 Correct 61 ms 22396 KB Output is correct
14 Correct 49 ms 22364 KB Output is correct
15 Correct 6815 ms 26276 KB Output is correct
16 Execution timed out 20014 ms 26496 KB Time limit exceeded
17 Halted 0 ms 0 KB -