oj.uz

답안 #836028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836028 2023-08-24T05:23:55 Z definitelynotmee 웜뱃 (IOI13_wombats) C++17
28 / 100
 1335 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;
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 < n; 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;
    }
};

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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 89 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 1 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 11 ms 21420 KB Output is correct
5 Correct 11 ms 21460 KB Output is correct
6 Correct 11 ms 21460 KB Output is correct
7 Correct 11 ms 21460 KB Output is correct
8 Correct 11 ms 20436 KB Output is correct
9 Correct 11 ms 20564 KB Output is correct
10 Correct 11 ms 21460 KB Output is correct
11 Correct 65 ms 22476 KB Output is correct
12 Correct 11 ms 21460 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 465 ms 96984 KB Output is correct
2 Correct 303 ms 97100 KB Output is correct
3 Correct 478 ms 97916 KB Output is correct
4 Correct 336 ms 97932 KB Output is correct
5 Correct 392 ms 97928 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 1 ms 3412 KB Output is correct
9 Correct 1335 ms 97928 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 88 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 401 ms 96988 KB Output is correct
2 Correct 311 ms 96992 KB Output is correct
3 Correct 487 ms 97932 KB Output is correct
4 Correct 332 ms 97932 KB Output is correct
5 Correct 390 ms 97928 KB Output is correct
6 Runtime error 90 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 402 ms 96972 KB Output is correct
2 Correct 316 ms 96984 KB Output is correct
3 Correct 482 ms 97932 KB Output is correct
4 Correct 333 ms 97932 KB Output is correct
5 Correct 399 ms 97936 KB Output is correct
6 Runtime error 90 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -