oj.uz

Submission #836078

# Submission time Handle Problem Language Result Execution time Memory
836078 2023-08-24T07:01:07 Z definitelynotmee Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 179480 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;
    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

# Verdict Execution time Memory Grader output
1 Correct 503 ms 166672 KB Output is correct
2 Correct 506 ms 166800 KB Output is correct
3 Correct 573 ms 168332 KB Output is correct
4 Correct 512 ms 166672 KB Output is correct
5 Correct 504 ms 166800 KB Output is correct
6 Correct 2 ms 2712 KB Output is correct
7 Correct 2 ms 2756 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 1 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 2 ms 3096 KB Output is correct
6 Correct 3 ms 3096 KB Output is correct
7 Correct 3 ms 3096 KB Output is correct
8 Correct 3 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 4108 KB Output is correct
12 Correct 4 ms 3096 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 7448 KB Output is correct
2 Correct 628 ms 7448 KB Output is correct
3 Correct 680 ms 7320 KB Output is correct
4 Correct 632 ms 7448 KB Output is correct
5 Correct 656 ms 7448 KB Output is correct
6 Correct 2 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 3002 ms 7448 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 526 ms 170864 KB Output is correct
2 Correct 520 ms 170860 KB Output is correct
3 Correct 545 ms 170892 KB Output is correct
4 Correct 562 ms 171628 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 7448 KB Output is correct
2 Correct 601 ms 7448 KB Output is correct
3 Correct 687 ms 7448 KB Output is correct
4 Correct 642 ms 7448 KB Output is correct
5 Correct 652 ms 7448 KB Output is correct
6 Correct 521 ms 170768 KB Output is correct
7 Correct 517 ms 170856 KB Output is correct
8 Correct 537 ms 170768 KB Output is correct
9 Correct 555 ms 171644 KB Output is correct
10 Correct 508 ms 166792 KB Output is correct
11 Correct 522 ms 166672 KB Output is correct
12 Correct 566 ms 168332 KB Output is correct
13 Correct 525 ms 166800 KB Output is correct
14 Correct 509 ms 166796 KB Output is correct
15 Correct 1 ms 2712 KB Output is correct
16 Correct 1 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 2 ms 3096 KB Output is correct
20 Correct 3 ms 3096 KB Output is correct
21 Correct 2 ms 3096 KB Output is correct
22 Correct 2 ms 3096 KB Output is correct
23 Correct 2 ms 3096 KB Output is correct
24 Correct 3 ms 3096 KB Output is correct
25 Correct 58 ms 4112 KB Output is correct
26 Correct 3 ms 3096 KB Output is correct
27 Correct 2998 ms 7448 KB Output is correct
28 Correct 6719 ms 175180 KB Output is correct
29 Correct 6400 ms 144652 KB Output is correct
30 Correct 6414 ms 144520 KB Output is correct
31 Correct 6735 ms 176036 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 632 ms 7428 KB Output is correct
2 Correct 627 ms 7572 KB Output is correct
3 Correct 681 ms 7448 KB Output is correct
4 Correct 674 ms 7320 KB Output is correct
5 Correct 705 ms 7320 KB Output is correct
6 Correct 522 ms 170860 KB Output is correct
7 Correct 512 ms 170944 KB Output is correct
8 Correct 534 ms 170860 KB Output is correct
9 Correct 553 ms 171760 KB Output is correct
10 Correct 511 ms 166672 KB Output is correct
11 Correct 515 ms 166788 KB Output is correct
12 Correct 560 ms 168332 KB Output is correct
13 Correct 513 ms 166800 KB Output is correct
14 Correct 514 ms 166796 KB Output is correct
15 Correct 13708 ms 178528 KB Output is correct
16 Execution timed out 20040 ms 179480 KB Time limit exceeded
17 Halted 0 ms 0 KB -