oj.uz

답안 #819972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
819972 2023-08-10T16:42:04 Z I_Love_EliskaM_ 웜뱃 (IOI13_wombats) C++17
55 / 100
 20000 ms 190012 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=10000;
const int C=205;

int opt[C][C];

int n,c;
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());
    }
    node merge(node&a, node&b) {
        if (b.empty) return a;
        if (a.empty) return b;
        node n;
        n.empty=0;
        n.v.assign(c,vector<int>(c,inf));
        forn(i,c) {
            forn(j,c) {
                if (a.v[i][j]+b.v[j][i] < n.v[i][i]) {
                    n.v[i][i] = a.v[i][j]+b.v[j][i];
                    opt[i][i]=j;
                }
            }
        }
        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 (a.v[l][m]+b.v[m][r] < n.v[l][r]) {
                        n.v[l][r] = a.v[l][m]+b.v[m][r];
                        opt[l][r] = m;
                    }
                }
            }
            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 (a.v[r][m]+b.v[m][l] < n.v[r][l]) {
                        n.v[r][l] = a.v[r][m]+b.v[m][l];
                        opt[r][l] = m;
                    }
                }
            }
        }
        return n;
    }

    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);
        t[v]=merge(t[2*v+1],t[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;

    for(int j=i; j<min(i+K,n-1); ++j) {
        forn(p,c) {
            vis.reset();
            priority_queue<pi> q;
            q.push({0,p});
            while (q.size()) {
                auto it=q.top(); q.pop();
                int u=it.s, di=-it.f;
                if (vis[u]) continue;
                vis[u]=1;
                if (u<c) {
                    if (u) q.push({-di-h[j][u-1],u-1});
                    if (u<c-1) q.push({-di-h[j][u],u+1});
                    q.push({-di-v[j][u],u+c});
                } else {
                    d[p+c*(j-i)][u-c]=di;
                    if (u-c) q.push({-di-h[j+1][u-c-1],u-1});
                    if (u-c<c-1) q.push({-di-h[j+1][u-c],u+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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8276 KB Output is correct
2 Correct 5 ms 8276 KB Output is correct
3 Correct 59 ms 9868 KB Output is correct
4 Correct 5 ms 8276 KB Output is correct
5 Correct 7 ms 8276 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 664 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 652 KB Output is correct
11 Correct 55 ms 1564 KB Output is correct
12 Correct 2 ms 596 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1800 ms 2924 KB Output is correct
2 Correct 2945 ms 2904 KB Output is correct
3 Correct 2157 ms 2980 KB Output is correct
4 Correct 1826 ms 2856 KB Output is correct
5 Correct 1965 ms 2912 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 13578 ms 3004 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16380 KB Output is correct
2 Correct 11 ms 16340 KB Output is correct
3 Correct 12 ms 16388 KB Output is correct
4 Correct 38 ms 17092 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1852 ms 2928 KB Output is correct
2 Correct 2947 ms 2904 KB Output is correct
3 Correct 2199 ms 2924 KB Output is correct
4 Correct 1911 ms 2924 KB Output is correct
5 Correct 1959 ms 2904 KB Output is correct
6 Correct 11 ms 16340 KB Output is correct
7 Correct 12 ms 16344 KB Output is correct
8 Correct 14 ms 16384 KB Output is correct
9 Correct 39 ms 17156 KB Output is correct
10 Correct 5 ms 8276 KB Output is correct
11 Correct 5 ms 8276 KB Output is correct
12 Correct 59 ms 9956 KB Output is correct
13 Correct 6 ms 8276 KB Output is correct
14 Correct 5 ms 8312 KB Output is correct
15 Correct 1 ms 356 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 664 KB Output is correct
23 Correct 3 ms 668 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 67 ms 1620 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 14189 ms 2932 KB Output is correct
28 Execution timed out 20064 ms 64460 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1911 ms 2928 KB Output is correct
2 Correct 3089 ms 2904 KB Output is correct
3 Correct 2235 ms 3008 KB Output is correct
4 Correct 2005 ms 2936 KB Output is correct
5 Correct 2037 ms 2908 KB Output is correct
6 Correct 12 ms 16340 KB Output is correct
7 Correct 15 ms 16316 KB Output is correct
8 Correct 16 ms 16372 KB Output is correct
9 Correct 42 ms 17160 KB Output is correct
10 Correct 5 ms 8276 KB Output is correct
11 Correct 5 ms 8276 KB Output is correct
12 Correct 64 ms 10052 KB Output is correct
13 Correct 7 ms 8308 KB Output is correct
14 Correct 6 ms 8276 KB Output is correct
15 Execution timed out 20018 ms 190012 KB Time limit exceeded
16 Halted 0 ms 0 KB -