oj.uz

답안 #836054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836054 2023-08-24T06:36:05 Z definitelynotmee 웜뱃 (IOI13_wombats) C++17
76 / 100
 20000 ms 230860 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);
    }
};

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;
int len, 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 antes = build_in_row(l), depois(m);

    matriz res(m,INF);

    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);
        matriz cur = build_next(i,antes,depois);
        res = res*cur;

        antes.swap(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];
        }
    }
    len = 15;
    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;

    for(int i = max(0,bid-1); i < min(bid+1,bct); i++)
        buildblock(i);
}

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;
      |      ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 657 ms 218620 KB Output is correct
2 Correct 634 ms 218624 KB Output is correct
3 Correct 661 ms 220160 KB Output is correct
4 Correct 627 ms 218612 KB Output is correct
5 Correct 603 ms 218608 KB Output is correct
6 Correct 1 ms 2772 KB Output is correct
7 Correct 1 ms 2772 KB Output is correct
8 Correct 1 ms 2772 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 59 ms 5196 KB Output is correct
12 Correct 3 ms 4180 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1243 ms 7588 KB Output is correct
2 Correct 820 ms 7580 KB Output is correct
3 Correct 1501 ms 7592 KB Output is correct
4 Correct 941 ms 7580 KB Output is correct
5 Correct 1071 ms 7508 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2772 KB Output is correct
9 Correct 5489 ms 7592 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 759 ms 222680 KB Output is correct
2 Correct 608 ms 222804 KB Output is correct
3 Correct 797 ms 222688 KB Output is correct
4 Correct 797 ms 223428 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1248 ms 7584 KB Output is correct
2 Correct 818 ms 7580 KB Output is correct
3 Correct 1503 ms 7588 KB Output is correct
4 Correct 866 ms 7588 KB Output is correct
5 Correct 1014 ms 7584 KB Output is correct
6 Correct 824 ms 222688 KB Output is correct
7 Correct 604 ms 222684 KB Output is correct
8 Correct 786 ms 222796 KB Output is correct
9 Correct 787 ms 223416 KB Output is correct
10 Correct 601 ms 218612 KB Output is correct
11 Correct 608 ms 218608 KB Output is correct
12 Correct 665 ms 220236 KB Output is correct
13 Correct 632 ms 218572 KB Output is correct
14 Correct 609 ms 218572 KB Output is correct
15 Correct 1 ms 2772 KB Output is correct
16 Correct 1 ms 2772 KB Output is correct
17 Correct 1 ms 2772 KB Output is correct
18 Correct 3 ms 4180 KB Output is correct
19 Correct 4 ms 4180 KB Output is correct
20 Correct 3 ms 4180 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 3 ms 4180 KB Output is correct
23 Correct 3 ms 4180 KB Output is correct
24 Correct 3 ms 4180 KB Output is correct
25 Correct 62 ms 5324 KB Output is correct
26 Correct 3 ms 4180 KB Output is correct
27 Correct 5392 ms 7508 KB Output is correct
28 Correct 10503 ms 226692 KB Output is correct
29 Correct 9544 ms 186460 KB Output is correct
30 Correct 9505 ms 187116 KB Output is correct
31 Correct 9619 ms 227716 KB Output is correct
32 Correct 2 ms 2772 KB Output is correct

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1291 ms 7708 KB Output is correct
2 Correct 836 ms 7508 KB Output is correct
3 Correct 1486 ms 7508 KB Output is correct
4 Correct 865 ms 7584 KB Output is correct
5 Correct 1014 ms 7580 KB Output is correct
6 Correct 776 ms 222680 KB Output is correct
7 Correct 614 ms 222644 KB Output is correct
8 Correct 793 ms 222684 KB Output is correct
9 Correct 791 ms 223436 KB Output is correct
10 Correct 616 ms 218688 KB Output is correct
11 Correct 611 ms 218496 KB Output is correct
12 Correct 670 ms 220208 KB Output is correct
13 Correct 619 ms 218620 KB Output is correct
14 Correct 595 ms 218608 KB Output is correct
15 Correct 12682 ms 230352 KB Output is correct
16 Execution timed out 20034 ms 230860 KB Time limit exceeded
17 Halted 0 ms 0 KB -