oj.uz

Submission #819980

# Submission time Handle Problem Language Result Execution time Memory
819980 2023-08-10T16:53:27 Z I_Love_EliskaM_ Wombats (IOI13_wombats) C++17
100 / 100
 9242 ms 193956 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second

const int inf=1e9;

const int N=5120;
const int C=205;

int opt[C][C];

int n,c;

int getopt(int i, int j) {
    if (i<0 || j<0) return 0;
    if (i>=c || j>=c) return c-1;
    return opt[i][j];
}

struct sgt {

    struct node {
        int empty=1;
        vector<vector<int>> v; 
        node() {
            empty=1;
        }
    };
    vector<node> t; int sz=1;
    sgt(int n) {
        while (sz<n) sz<<=1;
        t.assign(2*sz,node());
    }
    void merge(int v, int a, int b) {
        if (t[b].empty) {
            t[v]=t[a];
            return;
        }
        if (t[a].empty) {
            t[v]=t[b];
            return;
        }
        t[v].empty=0;
        t[v].v.assign(c,vector<int>(c,inf));
        for (int k=-c+1; k<c; ++k) {
            for (int l=0; l<c; ++l) {
                int r = l-k;
                if (r<0 || r>=c) continue;
                for (int m=getopt(l-1,r); m<=getopt(l,r+1); ++m) {
                    if (t[a].v[l][m]+t[b].v[m][r] < t[v].v[l][r]) {
                        t[v].v[l][r] = t[a].v[l][m]+t[b].v[m][r];
                        opt[l][r] = m;
                    }
                }
            }
        }
    }

    void upd(int v, int l, int r, int i) {
        if (r-l==1) return;
        int m=(l+r)>>1;
        if (i<m) upd(2*v+1,l,m,i);
        else upd(2*v+2,m,r,i);
        merge(v,2*v+1,2*v+2);
    }
    void set(int i, vector<vector<int>>&v) {
        t[sz-1+i].v=v;
        t[sz-1+i].empty=0;
        upd(0,0,sz,i);
    }

};

const int K=10;
sgt st(N/K);

int d[K*C][C];

int h[N][C];
int v[N][C];
bitset<2*C> vis;

void work(int i) {
    vector<vector<int>> t(c,vector<int>(c,1e9));

    if (i>=n-1) return;

    forn(i,K*c) forn(j,c) d[i][j]=inf;
    for(int j=i; j<min(i+K,n-1); ++j) {
        forn(p,c) {
            d[p+(j-i)*c][p]=0;
            for (int q=0; q<c-1; ++q) {
                d[p+(j-i)*c][q+1]=min(d[p+(j-i)*c][q+1],d[p+(j-i)*c][q]+h[j][q]);
            }
            for (int q=c-1; q>0; --q) {
                d[p+(j-i)*c][q-1]=min(d[p+(j-i)*c][q-1],d[p+(j-i)*c][q]+h[j][q-1]);
            }
            forn(q,c) d[p+(j-i)*c][q]+=v[j][q];
            for (int q=0; q<c-1; ++q) {
                d[p+(j-i)*c][q+1]=min(d[p+(j-i)*c][q+1],d[p+(j-i)*c][q]+h[j+1][q]);
            }
            for (int q=c-1; q>0; --q) {
                d[p+(j-i)*c][q-1]=min(d[p+(j-i)*c][q-1],d[p+(j-i)*c][q]+h[j+1][q-1]);
            }
        }
    }
    auto f=t;
    auto s=f;
    forn(p,c) forn(q,c) s[p][q]=d[p][q];
    for(int j=i+1; j<min(i+K,n-1); ++j) {
        forn(p,c) {
            forn(q,c) {
                if (s[p][q]+d[q+(j-i)*c][p] < f[p][p]) {
                    f[p][p] = s[p][q]+d[q+(j-i)*c][p];
                    opt[p][p] = q;
                }
            }
        }
        for(int k=1; k<c; ++k) {
            for (int l=0; l+k<c; ++l) {
                int r=l+k;
        
                for (int m=opt[l][r-1]; m<=opt[l+1][r]; ++m) {
                    if (s[l][m]+d[m+(j-i)*c][r] < f[l][r]) {
                        f[l][r] = s[l][m]+d[m+(j-i)*c][r];
                        opt[l][r]=m;
                    }
                }
            }
        }
        for(int k=1; k<c; ++k) {
            for (int l=0; l+k<c; ++l) {
                int r=l+k;
        
                for (int m=opt[r-1][l]; m<=opt[r][l+1]; ++m) {
                    if (s[r][m]+d[m+(j-i)*c][l] < f[r][l]) {
                        f[r][l] = s[r][m]+d[m+(j-i)*c][l];
                        opt[r][l]=m;
                    }
                }
            }
        }
        s=f;
        f=t;
    }
    st.set(i/K,s);
}

void init(int _n, int _c, int _h[][200], int _v[][200]) {
    n=_n, c=_c;
    forn(i,n) forn(j,c-1) h[i][j]=_h[i][j];
    forn(i,n-1) forn(j,c) v[i][j]=_v[i][j];

    for (int i=0; i<n-1; i+=K) {
        work(i);
    }

}

void changeH(int i, int j, int w) {

    h[i][j]=w;
    work((i/K)*K);
    if ((i+1)/K*K != i/K*K) work((i+1)/K*K);
    if (i) if ((i-1)/K*K != i/K*K) work((i-1)/K*K);

}
void changeV(int i, int j, int w) {
        
    v[i][j]=w;
    work((i/K)*K);

}

int escape(int i, int j) {
    return st.t[0].v[i][j];
}

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 4 ms 8276 KB Output is correct
2 Correct 4 ms 8276 KB Output is correct
3 Correct 56 ms 9996 KB Output is correct
4 Correct 7 ms 8404 KB Output is correct
5 Correct 4 ms 8296 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 53 ms 1640 KB Output is correct
12 Correct 1 ms 596 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 3004 KB Output is correct
2 Correct 156 ms 2788 KB Output is correct
3 Correct 236 ms 2760 KB Output is correct
4 Correct 204 ms 2900 KB Output is correct
5 Correct 210 ms 2772 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 848 ms 2892 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16340 KB Output is correct
2 Correct 9 ms 16340 KB Output is correct
3 Correct 10 ms 16340 KB Output is correct
4 Correct 37 ms 17160 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 3012 KB Output is correct
2 Correct 158 ms 2892 KB Output is correct
3 Correct 237 ms 2880 KB Output is correct
4 Correct 204 ms 2892 KB Output is correct
5 Correct 212 ms 2872 KB Output is correct
6 Correct 9 ms 16340 KB Output is correct
7 Correct 9 ms 16292 KB Output is correct
8 Correct 10 ms 16340 KB Output is correct
9 Correct 37 ms 17172 KB Output is correct
10 Correct 5 ms 8276 KB Output is correct
11 Correct 5 ms 8276 KB Output is correct
12 Correct 56 ms 10028 KB Output is correct
13 Correct 5 ms 8392 KB Output is correct
14 Correct 4 ms 8276 KB Output is correct
15 Correct 0 ms 376 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 53 ms 1740 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 880 ms 2880 KB Output is correct
28 Correct 2005 ms 60864 KB Output is correct
29 Correct 2183 ms 53892 KB Output is correct
30 Correct 2151 ms 53576 KB Output is correct
31 Correct 1981 ms 66252 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 2844 KB Output is correct
2 Correct 155 ms 3032 KB Output is correct
3 Correct 236 ms 2900 KB Output is correct
4 Correct 198 ms 2884 KB Output is correct
5 Correct 227 ms 2876 KB Output is correct
6 Correct 9 ms 16412 KB Output is correct
7 Correct 9 ms 16340 KB Output is correct
8 Correct 11 ms 16340 KB Output is correct
9 Correct 36 ms 17232 KB Output is correct
10 Correct 5 ms 8276 KB Output is correct
11 Correct 4 ms 8296 KB Output is correct
12 Correct 59 ms 10060 KB Output is correct
13 Correct 4 ms 8276 KB Output is correct
14 Correct 4 ms 8292 KB Output is correct
15 Correct 3573 ms 183312 KB Output is correct
16 Correct 9242 ms 193956 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 616 KB Output is correct
22 Correct 1 ms 616 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 612 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 56 ms 2892 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 896 ms 2900 KB Output is correct
30 Correct 2078 ms 64460 KB Output is correct
31 Correct 7997 ms 191308 KB Output is correct
32 Correct 7950 ms 191400 KB Output is correct
33 Correct 2181 ms 53756 KB Output is correct
34 Correct 8617 ms 158864 KB Output is correct
35 Correct 2151 ms 53696 KB Output is correct
36 Correct 8359 ms 158900 KB Output is correct
37 Correct 2041 ms 66428 KB Output is correct
38 Correct 8048 ms 192076 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 9051 ms 158876 KB Output is correct