oj.uz

Submission #836023

# Submission time Handle Problem Language Result Execution time Memory
836023 2023-08-24T05:13:24 Z definitelynotmee Wombats (IOI13_wombats) C++17
55 / 100
 1260 ms 262144 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;

struct matriz{
    matrix<int> v;

    matriz(int n = 0, int val = INF){
        v = matrix<int>(n,vector<int>(n,val));
    }

    matriz operator*(matriz & other){
        const int n = v.size();
        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;
    }
};

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;

vector<matriz> inrow;
vector<matriz> nextrow;

matrix<int> hor;
matrix<int> ver;

void build_in_row(int linha){
    inrow[linha] = matriz(m,0);
    for(int j = 0; j < m; j++){
        int cur = 0;

        for(int k = j; k < m-1; k++){
            cur+=hor[linha][k];
            inrow[linha].v[j][k+1] = inrow[linha].v[k+1][j] = cur;
        }
    }
}

void build_next(int linha){
    matriz col(m);

    for(int i = 0; i < m; i++)
        col.v[i][i] = ver[linha][i];
    
    nextrow[linha] = inrow[linha]*col*
    inrow[linha+1];

    st.makeupd(linha,nextrow[linha]);
}

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];
        }
    }

    inrow = vector<matriz>(n,matriz(m,0));

    // cerr << "ok" << endl;

    for(int i = 0; i < n; i++){
        // cerr << i << endl;
        build_in_row(i);
    }

    nextrow = vector<matriz>(n-1,matriz(m,0));

    st = SegTree(n-1,m);
    
    for(int i = 0; i < n-1; i++){
        // cerr << i << endl;
        build_next(i);
    }

}

void changeH(int P, int Q, int W) {
    // cerr << P << ' ' << Q << endl;
    hor[P][Q] = W;
    build_in_row(P);
    if(P != n-1)
        build_next(P);
    if(P != 0)
        build_next(P-1);
}

void changeV(int P, int Q, int W) {
    // cerr << P << ' ' << Q << endl;
    ver[P][Q] = W;
    build_next(P);
}

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 11 ms 7124 KB Output is correct
2 Correct 11 ms 7204 KB Output is correct
3 Correct 62 ms 9420 KB Output is correct
4 Correct 11 ms 7124 KB Output is correct
5 Correct 11 ms 7124 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 55 ms 1556 KB Output is correct
12 Correct 1 ms 568 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 26092 KB Output is correct
2 Correct 245 ms 25844 KB Output is correct
3 Correct 438 ms 26392 KB Output is correct
4 Correct 301 ms 26368 KB Output is correct
5 Correct 350 ms 26096 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1239 ms 26400 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 13140 KB Output is correct
2 Correct 19 ms 13148 KB Output is correct
3 Correct 19 ms 13152 KB Output is correct
4 Correct 48 ms 13932 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 26140 KB Output is correct
2 Correct 250 ms 25832 KB Output is correct
3 Correct 446 ms 26364 KB Output is correct
4 Correct 297 ms 26372 KB Output is correct
5 Correct 352 ms 26068 KB Output is correct
6 Correct 19 ms 13140 KB Output is correct
7 Correct 19 ms 13156 KB Output is correct
8 Correct 19 ms 13080 KB Output is correct
9 Correct 46 ms 13840 KB Output is correct
10 Correct 11 ms 7244 KB Output is correct
11 Correct 11 ms 7232 KB Output is correct
12 Correct 62 ms 9996 KB Output is correct
13 Correct 11 ms 7124 KB Output is correct
14 Correct 11 ms 7232 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 568 KB Output is correct
19 Correct 2 ms 568 KB Output is correct
20 Correct 2 ms 560 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 2 ms 572 KB Output is correct
24 Correct 3 ms 600 KB Output is correct
25 Correct 61 ms 2988 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 1260 ms 26476 KB Output is correct
28 Runtime error 222 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 26132 KB Output is correct
2 Correct 239 ms 25844 KB Output is correct
3 Correct 454 ms 26320 KB Output is correct
4 Correct 293 ms 26324 KB Output is correct
5 Correct 361 ms 26224 KB Output is correct
6 Correct 19 ms 13152 KB Output is correct
7 Correct 21 ms 13144 KB Output is correct
8 Correct 20 ms 13156 KB Output is correct
9 Correct 48 ms 13940 KB Output is correct
10 Correct 11 ms 7228 KB Output is correct
11 Correct 11 ms 7228 KB Output is correct
12 Correct 62 ms 9940 KB Output is correct
13 Correct 11 ms 7236 KB Output is correct
14 Correct 11 ms 7224 KB Output is correct
15 Runtime error 239 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -