oj.uz

Submission #836065

# Submission time Handle Problem Language Result Execution time Memory
836065 2023-08-24T06:51:39 Z definitelynotmee Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 179044 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;

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 antes = build_in_row(l), depois(m);

    matriz res(m,INF);

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

    for(int i = l; i < r; i++){
        depois = build_in_row(i+1);
        matriz cur = build_next(i,antes,depois);
        res = res*cur;

        antes.swap(depois);
    }

    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;

    for(int i = max(0,bid-1); i < min(bid+1,bct); i++)
        buildblock(i);
}

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

# Verdict Execution time Memory Grader output
1 Correct 506 ms 166792 KB Output is correct
2 Correct 546 ms 166800 KB Output is correct
3 Correct 583 ms 168340 KB Output is correct
4 Correct 524 ms 166788 KB Output is correct
5 Correct 521 ms 166888 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2712 KB Output is correct
2 Correct 2 ms 2712 KB Output is correct
3 Correct 1 ms 2712 KB Output is correct
4 Correct 3 ms 3096 KB Output is correct
5 Correct 3 ms 3096 KB Output is correct
6 Correct 3 ms 3096 KB Output is correct
7 Correct 2 ms 3096 KB Output is correct
8 Correct 2 ms 3096 KB Output is correct
9 Correct 3 ms 3096 KB Output is correct
10 Correct 3 ms 3096 KB Output is correct
11 Correct 57 ms 4036 KB Output is correct
12 Correct 3 ms 3096 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 7432 KB Output is correct
2 Correct 594 ms 7448 KB Output is correct
3 Correct 1155 ms 7448 KB Output is correct
4 Correct 642 ms 7448 KB Output is correct
5 Correct 798 ms 7448 KB Output is correct
6 Correct 1 ms 2712 KB Output is correct
7 Correct 2 ms 2712 KB Output is correct
8 Correct 1 ms 2712 KB Output is correct
9 Correct 4251 ms 7428 KB Output is correct
10 Correct 2 ms 2712 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 170860 KB Output is correct
2 Correct 550 ms 170864 KB Output is correct
3 Correct 644 ms 170868 KB Output is correct
4 Correct 645 ms 171660 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 7320 KB Output is correct
2 Correct 604 ms 7448 KB Output is correct
3 Correct 1122 ms 7448 KB Output is correct
4 Correct 633 ms 7448 KB Output is correct
5 Correct 810 ms 7320 KB Output is correct
6 Correct 634 ms 170920 KB Output is correct
7 Correct 520 ms 170856 KB Output is correct
8 Correct 647 ms 170860 KB Output is correct
9 Correct 664 ms 171584 KB Output is correct
10 Correct 523 ms 166800 KB Output is correct
11 Correct 512 ms 166788 KB Output is correct
12 Correct 570 ms 168364 KB Output is correct
13 Correct 530 ms 166792 KB Output is correct
14 Correct 557 ms 166796 KB Output is correct
15 Correct 2 ms 2712 KB Output is correct
16 Correct 2 ms 2712 KB Output is correct
17 Correct 1 ms 2712 KB Output is correct
18 Correct 3 ms 3096 KB Output is correct
19 Correct 3 ms 3096 KB Output is correct
20 Correct 3 ms 3096 KB Output is correct
21 Correct 3 ms 3096 KB Output is correct
22 Correct 3 ms 3096 KB Output is correct
23 Correct 3 ms 3096 KB Output is correct
24 Correct 3 ms 3096 KB Output is correct
25 Correct 57 ms 4108 KB Output is correct
26 Correct 3 ms 3096 KB Output is correct
27 Correct 4262 ms 7424 KB Output is correct
28 Correct 9291 ms 174964 KB Output is correct
29 Correct 8095 ms 144648 KB Output is correct
30 Correct 8077 ms 144564 KB Output is correct
31 Correct 8242 ms 175992 KB Output is correct
32 Correct 2 ms 2712 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 7432 KB Output is correct
2 Correct 607 ms 7320 KB Output is correct
3 Correct 1122 ms 7320 KB Output is correct
4 Correct 655 ms 7320 KB Output is correct
5 Correct 812 ms 7424 KB Output is correct
6 Correct 643 ms 170868 KB Output is correct
7 Correct 528 ms 170856 KB Output is correct
8 Correct 692 ms 170872 KB Output is correct
9 Correct 771 ms 171684 KB Output is correct
10 Correct 514 ms 166796 KB Output is correct
11 Correct 539 ms 166788 KB Output is correct
12 Correct 576 ms 168328 KB Output is correct
13 Correct 524 ms 166672 KB Output is correct
14 Correct 544 ms 166772 KB Output is correct
15 Correct 13467 ms 178528 KB Output is correct
16 Execution timed out 20064 ms 179044 KB Time limit exceeded
17 Halted 0 ms 0 KB -