oj.uz

Submission #836082

# Submission time Handle Problem Language Result Execution time Memory
836082 2023-08-24T07:05:43 Z definitelynotmee Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 181104 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 depois(m);

    matriz res = build_in_row(l);

    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);
        res = build_next(i,res,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 244 ms 167136 KB Output is correct
2 Correct 249 ms 167264 KB Output is correct
3 Correct 302 ms 168820 KB Output is correct
4 Correct 258 ms 167260 KB Output is correct
5 Correct 253 ms 167264 KB Output is correct
6 Correct 2 ms 3224 KB Output is correct
7 Correct 2 ms 3224 KB Output is correct
8 Correct 2 ms 3224 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3224 KB Output is correct
2 Correct 1 ms 3224 KB Output is correct
3 Correct 1 ms 3224 KB Output is correct
4 Correct 2 ms 3608 KB Output is correct
5 Correct 2 ms 3608 KB Output is correct
6 Correct 2 ms 3608 KB Output is correct
7 Correct 2 ms 3608 KB Output is correct
8 Correct 2 ms 3608 KB Output is correct
9 Correct 2 ms 3608 KB Output is correct
10 Correct 3 ms 3644 KB Output is correct
11 Correct 60 ms 4608 KB Output is correct
12 Correct 3 ms 3608 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 6976 KB Output is correct
2 Correct 425 ms 7064 KB Output is correct
3 Correct 484 ms 6936 KB Output is correct
4 Correct 432 ms 6968 KB Output is correct
5 Correct 516 ms 6936 KB Output is correct
6 Correct 3 ms 3224 KB Output is correct
7 Correct 1 ms 3224 KB Output is correct
8 Correct 1 ms 3224 KB Output is correct
9 Correct 2023 ms 6956 KB Output is correct
10 Correct 2 ms 3224 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 171328 KB Output is correct
2 Correct 256 ms 171328 KB Output is correct
3 Correct 273 ms 171336 KB Output is correct
4 Correct 297 ms 172108 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 6936 KB Output is correct
2 Correct 434 ms 6936 KB Output is correct
3 Correct 481 ms 6936 KB Output is correct
4 Correct 431 ms 6936 KB Output is correct
5 Correct 444 ms 6936 KB Output is correct
6 Correct 251 ms 171280 KB Output is correct
7 Correct 248 ms 171324 KB Output is correct
8 Correct 270 ms 171328 KB Output is correct
9 Correct 287 ms 172096 KB Output is correct
10 Correct 244 ms 167264 KB Output is correct
11 Correct 245 ms 167264 KB Output is correct
12 Correct 295 ms 168844 KB Output is correct
13 Correct 258 ms 167260 KB Output is correct
14 Correct 247 ms 167392 KB Output is correct
15 Correct 2 ms 3224 KB Output is correct
16 Correct 2 ms 3224 KB Output is correct
17 Correct 2 ms 3224 KB Output is correct
18 Correct 2 ms 3608 KB Output is correct
19 Correct 2 ms 3608 KB Output is correct
20 Correct 2 ms 3608 KB Output is correct
21 Correct 2 ms 3608 KB Output is correct
22 Correct 2 ms 3608 KB Output is correct
23 Correct 2 ms 3608 KB Output is correct
24 Correct 2 ms 3608 KB Output is correct
25 Correct 56 ms 4624 KB Output is correct
26 Correct 2 ms 3608 KB Output is correct
27 Correct 2076 ms 6936 KB Output is correct
28 Correct 4881 ms 175416 KB Output is correct
29 Correct 4744 ms 145100 KB Output is correct
30 Correct 4551 ms 145080 KB Output is correct
31 Correct 4911 ms 176460 KB Output is correct
32 Correct 2 ms 3224 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 6960 KB Output is correct
2 Correct 408 ms 6956 KB Output is correct
3 Correct 462 ms 6936 KB Output is correct
4 Correct 437 ms 6936 KB Output is correct
5 Correct 450 ms 6936 KB Output is correct
6 Correct 250 ms 171412 KB Output is correct
7 Correct 258 ms 171280 KB Output is correct
8 Correct 272 ms 171444 KB Output is correct
9 Correct 281 ms 172044 KB Output is correct
10 Correct 262 ms 167184 KB Output is correct
11 Correct 240 ms 167260 KB Output is correct
12 Correct 302 ms 168784 KB Output is correct
13 Correct 262 ms 167184 KB Output is correct
14 Correct 248 ms 167240 KB Output is correct
15 Correct 10238 ms 178992 KB Output is correct
16 Execution timed out 20029 ms 181104 KB Time limit exceeded
17 Halted 0 ms 0 KB -