oj.uz

Submission #836085

# Submission time Handle Problem Language Result Execution time Memory
836085 2023-08-24T07:09:24 Z definitelynotmee Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 247596 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 = 7;
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 289 ms 234584 KB Output is correct
2 Correct 283 ms 234276 KB Output is correct
3 Correct 346 ms 236132 KB Output is correct
4 Correct 296 ms 234584 KB Output is correct
5 Correct 287 ms 234660 KB Output is correct
6 Correct 1 ms 3224 KB Output is correct
7 Correct 1 ms 3224 KB Output is correct
8 Correct 1 ms 3224 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3224 KB Output is correct
2 Correct 2 ms 3224 KB Output is correct
3 Correct 1 ms 3224 KB Output is correct
4 Correct 2 ms 3864 KB Output is correct
5 Correct 3 ms 3864 KB Output is correct
6 Correct 2 ms 3864 KB Output is correct
7 Correct 2 ms 3864 KB Output is correct
8 Correct 2 ms 3884 KB Output is correct
9 Correct 2 ms 3864 KB Output is correct
10 Correct 2 ms 3864 KB Output is correct
11 Correct 56 ms 4840 KB Output is correct
12 Correct 2 ms 3864 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 8204 KB Output is correct
2 Correct 321 ms 8216 KB Output is correct
3 Correct 395 ms 8540 KB Output is correct
4 Correct 354 ms 8532 KB Output is correct
5 Correct 362 ms 8528 KB Output is correct
6 Correct 1 ms 3224 KB Output is correct
7 Correct 1 ms 3224 KB Output is correct
8 Correct 1 ms 3228 KB Output is correct
9 Correct 1593 ms 8528 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 285 ms 238348 KB Output is correct
2 Correct 287 ms 238668 KB Output is correct
3 Correct 305 ms 238644 KB Output is correct
4 Correct 321 ms 239400 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 8216 KB Output is correct
2 Correct 323 ms 8216 KB Output is correct
3 Correct 400 ms 8472 KB Output is correct
4 Correct 344 ms 8472 KB Output is correct
5 Correct 399 ms 8472 KB Output is correct
6 Correct 284 ms 238248 KB Output is correct
7 Correct 292 ms 238652 KB Output is correct
8 Correct 306 ms 238652 KB Output is correct
9 Correct 325 ms 239416 KB Output is correct
10 Correct 289 ms 234512 KB Output is correct
11 Correct 284 ms 234208 KB Output is correct
12 Correct 336 ms 236120 KB Output is correct
13 Correct 297 ms 234572 KB Output is correct
14 Correct 284 ms 234588 KB Output is correct
15 Correct 2 ms 3224 KB Output is correct
16 Correct 1 ms 3224 KB Output is correct
17 Correct 2 ms 3224 KB Output is correct
18 Correct 2 ms 3864 KB Output is correct
19 Correct 2 ms 3864 KB Output is correct
20 Correct 2 ms 3864 KB Output is correct
21 Correct 2 ms 3864 KB Output is correct
22 Correct 2 ms 3864 KB Output is correct
23 Correct 2 ms 3864 KB Output is correct
24 Correct 2 ms 3864 KB Output is correct
25 Correct 59 ms 4872 KB Output is correct
26 Correct 2 ms 3864 KB Output is correct
27 Correct 1575 ms 8528 KB Output is correct
28 Correct 4810 ms 242660 KB Output is correct
29 Correct 4517 ms 199896 KB Output is correct
30 Correct 4588 ms 200220 KB Output is correct
31 Correct 4910 ms 243680 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 365 ms 8216 KB Output is correct
2 Correct 327 ms 8216 KB Output is correct
3 Correct 396 ms 8528 KB Output is correct
4 Correct 344 ms 8532 KB Output is correct
5 Correct 378 ms 8532 KB Output is correct
6 Correct 289 ms 238224 KB Output is correct
7 Correct 284 ms 238580 KB Output is correct
8 Correct 302 ms 238736 KB Output is correct
9 Correct 323 ms 239384 KB Output is correct
10 Correct 284 ms 234516 KB Output is correct
11 Correct 286 ms 234252 KB Output is correct
12 Correct 333 ms 236164 KB Output is correct
13 Correct 291 ms 234516 KB Output is correct
14 Correct 284 ms 234576 KB Output is correct
15 Correct 11704 ms 246320 KB Output is correct
16 Execution timed out 20036 ms 247596 KB Time limit exceeded
17 Halted 0 ms 0 KB -