oj.uz

Submission #836049

# Submission time Handle Problem Language Result Execution time Memory
836049 2023-08-24T06:31:19 Z definitelynotmee Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 84016 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 = 50;
    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 1123 ms 72080 KB Output is correct
2 Correct 1141 ms 72076 KB Output is correct
3 Correct 1211 ms 73620 KB Output is correct
4 Correct 1175 ms 72004 KB Output is correct
5 Correct 1122 ms 72080 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 1 ms 2772 KB Output is correct
8 Correct 1 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 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2784 KB Output is correct
9 Correct 3 ms 2772 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Correct 59 ms 3788 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 4003 ms 4456 KB Output is correct
2 Correct 2446 ms 4428 KB Output is correct
3 Correct 3748 ms 4460 KB Output is correct
4 Correct 2598 ms 4452 KB Output is correct
5 Correct 2591 ms 4436 KB Output is correct
6 Correct 1 ms 2772 KB Output is correct
7 Correct 1 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 12406 ms 4436 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1646 ms 76144 KB Output is correct
2 Correct 1146 ms 76144 KB Output is correct
3 Correct 1673 ms 76236 KB Output is correct
4 Correct 1594 ms 76852 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4045 ms 4580 KB Output is correct
2 Correct 2527 ms 4456 KB Output is correct
3 Correct 4260 ms 4428 KB Output is correct
4 Correct 2626 ms 4432 KB Output is correct
5 Correct 2722 ms 4456 KB Output is correct
6 Correct 1668 ms 76152 KB Output is correct
7 Correct 1146 ms 76236 KB Output is correct
8 Correct 1633 ms 76180 KB Output is correct
9 Correct 1575 ms 76936 KB Output is correct
10 Correct 1136 ms 72008 KB Output is correct
11 Correct 1131 ms 72012 KB Output is correct
12 Correct 1188 ms 73612 KB Output is correct
13 Correct 1135 ms 72004 KB Output is correct
14 Correct 1150 ms 72092 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 3 ms 2772 KB Output is correct
19 Correct 3 ms 2772 KB Output is correct
20 Correct 3 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 2 ms 2772 KB Output is correct
25 Correct 58 ms 3760 KB Output is correct
26 Correct 2 ms 2772 KB Output is correct
27 Correct 12313 ms 4428 KB Output is correct
28 Execution timed out 20036 ms 80172 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3892 ms 4448 KB Output is correct
2 Correct 2475 ms 4456 KB Output is correct
3 Correct 3808 ms 4464 KB Output is correct
4 Correct 2598 ms 4452 KB Output is correct
5 Correct 2642 ms 4448 KB Output is correct
6 Correct 1722 ms 76144 KB Output is correct
7 Correct 1145 ms 76236 KB Output is correct
8 Correct 1633 ms 76136 KB Output is correct
9 Correct 1638 ms 76940 KB Output is correct
10 Correct 1155 ms 72000 KB Output is correct
11 Correct 1155 ms 72008 KB Output is correct
12 Correct 1205 ms 73656 KB Output is correct
13 Correct 1323 ms 72076 KB Output is correct
14 Correct 1217 ms 72004 KB Output is correct
15 Correct 11666 ms 83816 KB Output is correct
16 Execution timed out 20049 ms 84016 KB Time limit exceeded
17 Halted 0 ms 0 KB -