oj.uz

Submission #834882

# Submission time Handle Problem Language Result Execution time Memory
834882 2023-08-22T21:52:19 Z definitelynotmee Wombats (IOI13_wombats) C++17
12 / 100
 20000 ms 18476 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] = 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);
        
        return ret;
    }
};

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

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));

    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);
    build_next(P);
}

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;

    matriz resp = nextrow[0];

    for(int i = 1; i < n-1; i++){
        resp = resp*nextrow[i];
    }

    return resp.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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 5460 KB Output is correct
2 Correct 138 ms 5460 KB Output is correct
3 Execution timed out 20043 ms 6564 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 35 ms 340 KB Output is correct
5 Correct 35 ms 436 KB Output is correct
6 Correct 37 ms 468 KB Output is correct
7 Correct 35 ms 340 KB Output is correct
8 Correct 34 ms 428 KB Output is correct
9 Correct 41 ms 432 KB Output is correct
10 Correct 34 ms 440 KB Output is correct
11 Correct 19704 ms 2804 KB Output is correct
12 Correct 37 ms 340 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 18476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 547 ms 10220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 18468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 18460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -