oj.uz

답안 #836091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836091 2023-08-24T07:15:52 Z definitelynotmee 웜뱃 (IOI13_wombats) C++17
100 / 100
 14912 ms 187836 KB 
// #include "grader.c"
#include"wombats.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
using ll = long long;
using pii = pair<int,int>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1e9;
const int MAXN = 200;
template<typename T>
using mat = array<array<int,MAXN>,MAXN>;


struct matriz{
    mat<int> v;
    int n;
    matriz(int sz = 0, int val = INF){
        n = sz;
        for(int i = 0; i < sz; i++){
            fill(v[i].begin(), v[i].begin()+n, val);
        }
    }

    matriz operator*(matriz other){
        matriz ret(n);
        
        auto solve =[&](int source, int l, int r, int optl, int optr, auto solve) -> void {
            if(r < l)
                return;
            
            int m = (l+r)>>1;

            int opt = optl;

            for (int i = optl+1; i <= optr; i++)
                opt = min(opt,i,[&](int a, int b){
                    return v[source][a]+other.v[a][m] < v[source][b]+other.v[b][m]; 
                });
            
            ret.v[source][m] = min(INF,v[source][opt]+other.v[opt][m]);
            
            solve(source,m+1,r,opt,optr,solve);
            solve(source,l,m-1,optl,opt,solve);
        };

        for(int i = 0; i < n; i++)
            solve(i,0,n-1,0,n-1,solve);
        

        // for(int i = 0; i < n; i++){
        //     for(int j = 0; j < n; j++){
        //         for(int k = 0; k < n; k++){
        //             ret.v[i][j] = min(v[i][k]+other.v[k][j], ret.v[i][j]);
        //         }
        //     }
        // }

        return ret;
    }

    void swap(matriz& other){
        v.swap(other.v);
    }
};

int getmid(int l, int r){
    return min(l+(1<<__lg(r-l+1))-1, r-(1<<__lg(r-l+1)-1));
}

struct SegTree{
    vector<matriz> tree;

    int sz, q;

    matriz val;

    SegTree(int n = 0, int m = 0){
        sz = n;
        tree = vector<matriz>(2*n+2,matriz(m));
    }

    void update(int id, int l, int r){
        if(l > q || r < q)
            return;
        if(l == q && r == q){
            tree[id] = val;
            return;
        }

        int e = id*2+1, d = id*2+2, m = getmid(l,r);

        update(e,l,m);
        update(d,m+1,r);

        tree[id] = tree[e]*tree[d];
    }

    void makeupd(int id, matriz v){
        val = v;
        q = id;
        update(0,0,sz-1);
    }
}st;

matriz pogmerge(matriz m1, matriz m2, vector<int> col){
    int n = m1.n;
    matriz ret(n);
        
    auto solve =[&](int source, int l, int r, int optl, int optr, auto solve) -> void {
        if(r < l)
            return;
        
        int m = (l+r)>>1;

        int opt = optl;

        for (int i = optl+1; i <= optr; i++)
            opt = min(opt,i,[&](int a, int b){
                return m1.v[source][a]+m2.v[a][m]+col[a] < m1.v[source][b]+m2.v[b][m]+col[b]; 
            });
        
        ret.v[source][m] = min(INF,m1.v[source][opt]+m2.v[opt][m]+col[opt]);
        
        solve(source,m+1,r,opt,optr,solve);
        solve(source,l,m-1,optl,opt,solve);
    };

    for(int i = 0; i < n; i++)
        solve(i,0,n-1,0,n-1,solve);
    

    // for(int i = 0; i < n; i++){
    //     for(int j = 0; j < n; j++){
    //         for(int k = 0; k < n; k++){
    //             ret.v[i][j] = min(v[i][k]+other.v[k][j], ret.v[i][j]);
    //         }
    //     }
    // }

    return ret;
}

int n, m;
const int len = 10;
int bct;

matrix<int> hor;
matrix<int> ver;

matriz build_in_row(int linha){
    matriz ret(m,0);
    for(int j = 0; j < m; j++){
        int cur = 0;

        for(int k = j; k < m-1; k++){
            cur+=hor[linha][k];
            ret.v[j][k+1] = ret.v[k+1][j] = cur;
        }
    }
    return ret;
}

matriz build_next(int linha, matriz& antes, matriz& depois){
    matriz col(m);

    for(int i = 0; i < m; i++)
        col.v[i][i] = ver[linha][i];

    return antes*col*depois;
}

void buildblock(int bid){
    int l = bid*len, r = min((bid+1)*len,n-1);
    // cerr << bid << ' ' << l << ' ' << r << endl;

    matriz res = build_in_row(l);

    for(int i = 0; i < m; i++)
        res.v[i][i] = 0;

    for(int i = l; i < r; i++){
        res = pogmerge(res,build_in_row(i+1),ver[i]);

    }

    st.makeupd(bid,res);


    // cerr << l << ' ' << r << ":\n";
    // for(int i = 0; i < m; i++){
    //     for(int j = 0; j < m; j++){
    //         cerr << res.v[i][j] << ' ';
    //     }
    //     cerr << '\n';
    // }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    // cerr << "ok" << endl;

    n = R;
    m = C;

    // cerr << n << ' ' << m << endl;
    hor = matrix<int>(n,vector<int>(m-1));
    ver = matrix<int>(n-1,vector<int>(m));
    // cerr << "ok" << endl;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m-1; j++)
            hor[i][j] = H[i][j];
    }

    for(int i = 0; i < n-1; i++){
        for(int j = 0; j < m; j++){
            ver[i][j] = V[i][j];
        }
    }
    bct = (n-2+len)/len;

    st = SegTree(bct,m);

    for(int i = 0; i < bct; i++){
        buildblock(i);
    }
}

void changeH(int P, int Q, int W) {
    // cerr << P << ' ' << Q << endl;
    hor[P][Q] = W;
    int bid = P/len;
    int lastbid = (P-1)/len;

    if(bid<bct)
        buildblock(bid);
    if(bid!=lastbid)
        buildblock(lastbid);
}

void changeV(int P, int Q, int W) {
    // cerr << P << ' ' << Q << endl;
    ver[P][Q] = W;
    int bid = P/len;

    buildblock(bid);
}

int escape(int V1, int V2) {
    // cerr << V1 << ' ' << V2 << endl;

    return st.tree[0].v[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;
      |      ^~~
wombats.cpp: In function 'int getmid(int, int)':
wombats.cpp:71:55: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |     return min(l+(1<<__lg(r-l+1))-1, r-(1<<__lg(r-l+1)-1));
      |                                            ~~~~~~~~~~~^~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 167092 KB Output is correct
2 Correct 346 ms 167104 KB Output is correct
3 Correct 386 ms 168604 KB Output is correct
4 Correct 367 ms 167064 KB Output is correct
5 Correct 350 ms 167000 KB Output is correct
6 Correct 2 ms 2712 KB Output is correct
7 Correct 1 ms 2712 KB Output is correct
8 Correct 1 ms 2712 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2712 KB Output is correct
2 Correct 1 ms 2712 KB Output is correct
3 Correct 2 ms 2812 KB Output is correct
4 Correct 2 ms 3224 KB Output is correct
5 Correct 2 ms 3224 KB Output is correct
6 Correct 2 ms 3224 KB Output is correct
7 Correct 2 ms 3224 KB Output is correct
8 Correct 2 ms 3224 KB Output is correct
9 Correct 2 ms 3248 KB Output is correct
10 Correct 2 ms 3224 KB Output is correct
11 Correct 62 ms 4240 KB Output is correct
12 Correct 3 ms 3224 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 6936 KB Output is correct
2 Correct 310 ms 6956 KB Output is correct
3 Correct 321 ms 6936 KB Output is correct
4 Correct 301 ms 6936 KB Output is correct
5 Correct 306 ms 6936 KB Output is correct
6 Correct 1 ms 2712 KB Output is correct
7 Correct 1 ms 2712 KB Output is correct
8 Correct 1 ms 2712 KB Output is correct
9 Correct 1371 ms 6960 KB Output is correct
10 Correct 1 ms 2712 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 342 ms 171176 KB Output is correct
2 Correct 337 ms 171092 KB Output is correct
3 Correct 358 ms 171180 KB Output is correct
4 Correct 370 ms 171944 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 6960 KB Output is correct
2 Correct 293 ms 6936 KB Output is correct
3 Correct 324 ms 6964 KB Output is correct
4 Correct 306 ms 6908 KB Output is correct
5 Correct 318 ms 6936 KB Output is correct
6 Correct 338 ms 171172 KB Output is correct
7 Correct 335 ms 171256 KB Output is correct
8 Correct 360 ms 171180 KB Output is correct
9 Correct 373 ms 171868 KB Output is correct
10 Correct 331 ms 167096 KB Output is correct
11 Correct 331 ms 167116 KB Output is correct
12 Correct 378 ms 168616 KB Output is correct
13 Correct 348 ms 167112 KB Output is correct
14 Correct 326 ms 167104 KB Output is correct
15 Correct 2 ms 2756 KB Output is correct
16 Correct 1 ms 2712 KB Output is correct
17 Correct 1 ms 2712 KB Output is correct
18 Correct 2 ms 3224 KB Output is correct
19 Correct 2 ms 3224 KB Output is correct
20 Correct 2 ms 3224 KB Output is correct
21 Correct 2 ms 3224 KB Output is correct
22 Correct 2 ms 3224 KB Output is correct
23 Correct 2 ms 3324 KB Output is correct
24 Correct 2 ms 3224 KB Output is correct
25 Correct 54 ms 4248 KB Output is correct
26 Correct 2 ms 3224 KB Output is correct
27 Correct 1437 ms 6916 KB Output is correct
28 Correct 3604 ms 175328 KB Output is correct
29 Correct 3677 ms 144952 KB Output is correct
30 Correct 3442 ms 144920 KB Output is correct
31 Correct 3596 ms 176288 KB Output is correct
32 Correct 1 ms 2712 KB Output is correct

Subtask #6
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 297 ms 6964 KB Output is correct
2 Correct 298 ms 6916 KB Output is correct
3 Correct 316 ms 6936 KB Output is correct
4 Correct 299 ms 6892 KB Output is correct
5 Correct 309 ms 6912 KB Output is correct
6 Correct 330 ms 171180 KB Output is correct
7 Correct 325 ms 171172 KB Output is correct
8 Correct 370 ms 171176 KB Output is correct
9 Correct 371 ms 171864 KB Output is correct
10 Correct 333 ms 167108 KB Output is correct
11 Correct 325 ms 167048 KB Output is correct
12 Correct 379 ms 168644 KB Output is correct
13 Correct 347 ms 167032 KB Output is correct
14 Correct 327 ms 167108 KB Output is correct
15 Correct 7161 ms 178844 KB Output is correct
16 Correct 14912 ms 180452 KB Output is correct
17 Correct 1 ms 2712 KB Output is correct
18 Correct 2 ms 2780 KB Output is correct
19 Correct 2 ms 2712 KB Output is correct
20 Correct 2 ms 3224 KB Output is correct
21 Correct 2 ms 3296 KB Output is correct
22 Correct 2 ms 3224 KB Output is correct
23 Correct 2 ms 3224 KB Output is correct
24 Correct 2 ms 3224 KB Output is correct
25 Correct 2 ms 3224 KB Output is correct
26 Correct 2 ms 3224 KB Output is correct
27 Correct 54 ms 5588 KB Output is correct
28 Correct 2 ms 3224 KB Output is correct
29 Correct 1343 ms 7020 KB Output is correct
30 Correct 3549 ms 179000 KB Output is correct
31 Correct 14700 ms 187208 KB Output is correct
32 Correct 14008 ms 187224 KB Output is correct
33 Correct 3569 ms 148432 KB Output is correct
34 Correct 13555 ms 155560 KB Output is correct
35 Correct 3586 ms 148312 KB Output is correct
36 Correct 13618 ms 155568 KB Output is correct
37 Correct 3557 ms 180716 KB Output is correct
38 Correct 14335 ms 187836 KB Output is correct
39 Correct 2 ms 2840 KB Output is correct
40 Correct 13489 ms 155688 KB Output is correct