oj.uz

답안 #593928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
593928 2022-07-11T17:37:13 Z jeroenodb 웜뱃 (IOI13_wombats) C++14
100 / 100
 16564 ms 57916 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<17) {
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 52436 KB Output is correct
2 Correct 126 ms 52428 KB Output is correct
3 Correct 187 ms 54040 KB Output is correct
4 Correct 119 ms 52428 KB Output is correct
5 Correct 123 ms 52440 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 0 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 64 ms 1844 KB Output is correct
12 Correct 1 ms 852 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 1568 KB Output is correct
2 Correct 299 ms 1588 KB Output is correct
3 Correct 274 ms 1492 KB Output is correct
4 Correct 250 ms 1492 KB Output is correct
5 Correct 310 ms 1620 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 1499 ms 1492 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 56336 KB Output is correct
2 Correct 119 ms 56344 KB Output is correct
3 Correct 114 ms 56336 KB Output is correct
4 Correct 154 ms 57028 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 1492 KB Output is correct
2 Correct 295 ms 1492 KB Output is correct
3 Correct 285 ms 1492 KB Output is correct
4 Correct 253 ms 1564 KB Output is correct
5 Correct 294 ms 1596 KB Output is correct
6 Correct 134 ms 56352 KB Output is correct
7 Correct 131 ms 56344 KB Output is correct
8 Correct 125 ms 56348 KB Output is correct
9 Correct 141 ms 57120 KB Output is correct
10 Correct 114 ms 52476 KB Output is correct
11 Correct 106 ms 52440 KB Output is correct
12 Correct 179 ms 53980 KB Output is correct
13 Correct 112 ms 52340 KB Output is correct
14 Correct 116 ms 52436 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 66 ms 1740 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 1503 ms 1492 KB Output is correct
28 Correct 3342 ms 56592 KB Output is correct
29 Correct 2938 ms 34048 KB Output is correct
30 Correct 3048 ms 34048 KB Output is correct
31 Correct 3495 ms 57620 KB Output is correct
32 Correct 1 ms 724 KB Output is correct

Subtask #6
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 1572 KB Output is correct
2 Correct 333 ms 1592 KB Output is correct
3 Correct 319 ms 1568 KB Output is correct
4 Correct 282 ms 1492 KB Output is correct
5 Correct 336 ms 1572 KB Output is correct
6 Correct 130 ms 56348 KB Output is correct
7 Correct 123 ms 56344 KB Output is correct
8 Correct 187 ms 56340 KB Output is correct
9 Correct 177 ms 57104 KB Output is correct
10 Correct 115 ms 52408 KB Output is correct
11 Correct 127 ms 52436 KB Output is correct
12 Correct 199 ms 53932 KB Output is correct
13 Correct 133 ms 52436 KB Output is correct
14 Correct 121 ms 52428 KB Output is correct
15 Correct 2163 ms 56336 KB Output is correct
16 Correct 16082 ms 57916 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 1 ms 724 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 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 1 ms 852 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 80 ms 1820 KB Output is correct
28 Correct 1 ms 852 KB Output is correct
29 Correct 1630 ms 1588 KB Output is correct
30 Correct 3447 ms 56764 KB Output is correct
31 Correct 16145 ms 56964 KB Output is correct
32 Correct 14800 ms 57136 KB Output is correct
33 Correct 2948 ms 33872 KB Output is correct
34 Correct 13443 ms 34224 KB Output is correct
35 Correct 2859 ms 33844 KB Output is correct
36 Correct 13541 ms 34172 KB Output is correct
37 Correct 3465 ms 57620 KB Output is correct
38 Correct 16564 ms 57728 KB Output is correct
39 Correct 1 ms 724 KB Output is correct
40 Correct 14523 ms 34076 KB Output is correct