oj.uz

Submission #836061

# Submission time Handle Problem Language Result Execution time Memory
836061 2023-08-24T06:48:47 Z definitelynotmee Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 100708 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;
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 = 20;
    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 630 ms 88504 KB Output is correct
2 Correct 648 ms 88508 KB Output is correct
3 Correct 688 ms 90072 KB Output is correct
4 Correct 656 ms 88592 KB Output is correct
5 Correct 637 ms 88516 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

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1652 ms 4928 KB Output is correct
2 Correct 1077 ms 4888 KB Output is correct
3 Correct 1911 ms 4928 KB Output is correct
4 Correct 1212 ms 4924 KB Output is correct
5 Correct 1255 ms 4932 KB Output is correct
6 Correct 2 ms 2712 KB Output is correct
7 Correct 2 ms 2756 KB Output is correct
8 Correct 2 ms 2712 KB Output is correct
9 Correct 6288 ms 4944 KB Output is correct
10 Correct 3 ms 2712 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 92584 KB Output is correct
2 Correct 643 ms 92580 KB Output is correct
3 Correct 892 ms 92580 KB Output is correct
4 Correct 901 ms 93276 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1669 ms 4920 KB Output is correct
2 Correct 1062 ms 4924 KB Output is correct
3 Correct 1952 ms 4924 KB Output is correct
4 Correct 1226 ms 4832 KB Output is correct
5 Correct 1296 ms 4920 KB Output is correct
6 Correct 871 ms 92576 KB Output is correct
7 Correct 633 ms 92584 KB Output is correct
8 Correct 851 ms 92584 KB Output is correct
9 Correct 912 ms 93416 KB Output is correct
10 Correct 630 ms 88512 KB Output is correct
11 Correct 687 ms 88484 KB Output is correct
12 Correct 698 ms 90056 KB Output is correct
13 Correct 657 ms 88484 KB Output is correct
14 Correct 631 ms 88416 KB Output is correct
15 Correct 1 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 2840 KB Output is correct
19 Correct 2 ms 2840 KB Output is correct
20 Correct 3 ms 2840 KB Output is correct
21 Correct 2 ms 2840 KB Output is correct
22 Correct 2 ms 2840 KB Output is correct
23 Correct 3 ms 2840 KB Output is correct
24 Correct 3 ms 2840 KB Output is correct
25 Correct 67 ms 3732 KB Output is correct
26 Correct 2 ms 2840 KB Output is correct
27 Correct 6322 ms 4924 KB Output is correct
28 Correct 12898 ms 96660 KB Output is correct
29 Correct 11336 ms 80416 KB Output is correct
30 Correct 11353 ms 80436 KB Output is correct
31 Correct 11583 ms 97612 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 1786 ms 4956 KB Output is correct
2 Correct 1120 ms 4928 KB Output is correct
3 Correct 1964 ms 4888 KB Output is correct
4 Correct 1192 ms 4832 KB Output is correct
5 Correct 1295 ms 4836 KB Output is correct
6 Correct 874 ms 92592 KB Output is correct
7 Correct 705 ms 92580 KB Output is correct
8 Correct 902 ms 92588 KB Output is correct
9 Correct 907 ms 93348 KB Output is correct
10 Correct 668 ms 88464 KB Output is correct
11 Correct 636 ms 88512 KB Output is correct
12 Correct 695 ms 90176 KB Output is correct
13 Correct 677 ms 88496 KB Output is correct
14 Correct 633 ms 88504 KB Output is correct
15 Correct 12379 ms 100240 KB Output is correct
16 Execution timed out 20095 ms 100708 KB Time limit exceeded
17 Halted 0 ms 0 KB -