oj.uz

Submission #593922

# Submission time Handle Problem Language Result Execution time Memory
593922 2022-07-11T17:33:37 Z jeroenodb Wombats (IOI13_wombats) C++14
100 / 100
 15209 ms 67268 KB 
#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 = 75, 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<6) {
        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 133 ms 52448 KB Output is correct
2 Correct 124 ms 52412 KB Output is correct
3 Correct 209 ms 55236 KB Output is correct
4 Correct 131 ms 52440 KB Output is correct
5 Correct 127 ms 52464 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 816 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 76 ms 1812 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 148 ms 1580 KB Output is correct
2 Correct 337 ms 1492 KB Output is correct
3 Correct 295 ms 1492 KB Output is correct
4 Correct 293 ms 1492 KB Output is correct
5 Correct 313 ms 1492 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 1596 ms 1564 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 139 ms 56324 KB Output is correct
2 Correct 148 ms 56396 KB Output is correct
3 Correct 147 ms 56412 KB Output is correct
4 Correct 210 ms 57752 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 1568 KB Output is correct
2 Correct 327 ms 1592 KB Output is correct
3 Correct 307 ms 1492 KB Output is correct
4 Correct 278 ms 1592 KB Output is correct
5 Correct 419 ms 1584 KB Output is correct
6 Correct 139 ms 56344 KB Output is correct
7 Correct 150 ms 56420 KB Output is correct
8 Correct 170 ms 56420 KB Output is correct
9 Correct 157 ms 57780 KB Output is correct
10 Correct 121 ms 52448 KB Output is correct
11 Correct 126 ms 52372 KB Output is correct
12 Correct 247 ms 55240 KB Output is correct
13 Correct 131 ms 52428 KB Output is correct
14 Correct 153 ms 52464 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 2 ms 852 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 1 ms 836 KB Output is correct
22 Correct 1 ms 840 KB Output is correct
23 Correct 1 ms 844 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 79 ms 3220 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 1723 ms 1672 KB Output is correct
28 Correct 3422 ms 60476 KB Output is correct
29 Correct 3224 ms 37320 KB Output is correct
30 Correct 2834 ms 37220 KB Output is correct
31 Correct 3207 ms 62104 KB Output is correct
32 Correct 1 ms 700 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1564 KB Output is correct
2 Correct 314 ms 1588 KB Output is correct
3 Correct 307 ms 1492 KB Output is correct
4 Correct 300 ms 1492 KB Output is correct
5 Correct 319 ms 1492 KB Output is correct
6 Correct 121 ms 56236 KB Output is correct
7 Correct 124 ms 56480 KB Output is correct
8 Correct 141 ms 56412 KB Output is correct
9 Correct 156 ms 57676 KB Output is correct
10 Correct 110 ms 52428 KB Output is correct
11 Correct 127 ms 52436 KB Output is correct
12 Correct 187 ms 55240 KB Output is correct
13 Correct 113 ms 52424 KB Output is correct
14 Correct 110 ms 52460 KB Output is correct
15 Correct 1918 ms 66104 KB Output is correct
16 Correct 14852 ms 67268 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 708 KB Output is correct
19 Correct 1 ms 724 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 840 KB Output is correct
23 Correct 1 ms 832 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 1 ms 852 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 69 ms 3232 KB Output is correct
28 Correct 1 ms 852 KB Output is correct
29 Correct 1545 ms 1636 KB Output is correct
30 Correct 2962 ms 60480 KB Output is correct
31 Correct 13305 ms 64776 KB Output is correct
32 Correct 13514 ms 64680 KB Output is correct
33 Correct 3006 ms 37304 KB Output is correct
34 Correct 15209 ms 41356 KB Output is correct
35 Correct 3192 ms 37340 KB Output is correct
36 Correct 12807 ms 41248 KB Output is correct
37 Correct 2974 ms 62096 KB Output is correct
38 Correct 13123 ms 65260 KB Output is correct
39 Correct 1 ms 724 KB Output is correct
40 Correct 11910 ms 41456 KB Output is correct