oj.uz

Submission #836051

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

struct SegTree{
    vector<matriz> tree;

    int sz, q;

    matriz val;

    SegTree(int n = 0, int m = 0){
        sz = n;
        tree = vector<matriz>(4*n,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 =(l+r)>>1;

        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;
int len, 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];
        }
    }
    len = 25;
    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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 134696 KB Output is correct
2 Correct 782 ms 134704 KB Output is correct
3 Correct 820 ms 136236 KB Output is correct
4 Correct 860 ms 134696 KB Output is correct
5 Correct 765 ms 134672 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 1 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2844 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 63 ms 3784 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2056 ms 5720 KB Output is correct
2 Correct 1298 ms 5716 KB Output is correct
3 Correct 2290 ms 5716 KB Output is correct
4 Correct 1634 ms 5716 KB Output is correct
5 Correct 1375 ms 5716 KB Output is correct
6 Correct 1 ms 2772 KB Output is correct
7 Correct 1 ms 2772 KB Output is correct
8 Correct 1 ms 2772 KB Output is correct
9 Correct 7729 ms 5712 KB Output is correct
10 Correct 1 ms 2772 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 138764 KB Output is correct
2 Correct 887 ms 138764 KB Output is correct
3 Correct 1027 ms 138764 KB Output is correct
4 Correct 1308 ms 139568 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2611 ms 5716 KB Output is correct
2 Correct 1291 ms 5720 KB Output is correct
3 Correct 2429 ms 5708 KB Output is correct
4 Correct 1378 ms 5720 KB Output is correct
5 Correct 1371 ms 5716 KB Output is correct
6 Correct 987 ms 138856 KB Output is correct
7 Correct 750 ms 138764 KB Output is correct
8 Correct 1016 ms 138772 KB Output is correct
9 Correct 1004 ms 139560 KB Output is correct
10 Correct 742 ms 134696 KB Output is correct
11 Correct 738 ms 134700 KB Output is correct
12 Correct 785 ms 136292 KB Output is correct
13 Correct 759 ms 134696 KB Output is correct
14 Correct 741 ms 134696 KB Output is correct
15 Correct 1 ms 2772 KB Output is correct
16 Correct 1 ms 2772 KB Output is correct
17 Correct 1 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 2 ms 2772 KB Output is correct
20 Correct 2 ms 2772 KB Output is correct
21 Correct 2 ms 2772 KB Output is correct
22 Correct 2 ms 2772 KB Output is correct
23 Correct 2 ms 2772 KB Output is correct
24 Correct 3 ms 2776 KB Output is correct
25 Correct 59 ms 3788 KB Output is correct
26 Correct 2 ms 2772 KB Output is correct
27 Correct 7240 ms 5720 KB Output is correct
28 Correct 14764 ms 142988 KB Output is correct
29 Correct 13439 ms 121644 KB Output is correct
30 Correct 13232 ms 121632 KB Output is correct
31 Correct 13104 ms 148320 KB Output is correct
32 Correct 2 ms 2772 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2147 ms 5716 KB Output is correct
2 Correct 1303 ms 5712 KB Output is correct
3 Correct 2507 ms 5708 KB Output is correct
4 Correct 1408 ms 5716 KB Output is correct
5 Correct 1372 ms 5704 KB Output is correct
6 Correct 990 ms 138768 KB Output is correct
7 Correct 737 ms 138832 KB Output is correct
8 Correct 1073 ms 138768 KB Output is correct
9 Correct 1004 ms 139512 KB Output is correct
10 Correct 736 ms 134748 KB Output is correct
11 Correct 762 ms 134732 KB Output is correct
12 Correct 780 ms 136228 KB Output is correct
13 Correct 757 ms 134700 KB Output is correct
14 Correct 737 ms 134700 KB Output is correct
15 Correct 11674 ms 146432 KB Output is correct
16 Execution timed out 20093 ms 146748 KB Time limit exceeded
17 Halted 0 ms 0 KB -