oj.uz

Submission #790608

# Submission time Handle Problem Language Result Execution time Memory
790608 2023-07-23T00:30:33 Z Ronin13 Wombats (IOI13_wombats) C++17
0 / 100
 340 ms 262144 KB 
#include <bits/stdc++.h>
#include "wombats.h"
#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 5000;
int h[5000][200];
int v[5000][200];
int r, c;
int s;
struct node{
    //vector <int> h;
    vector <int> w;
    vector <vector <int> > cost;
    node(){
        cost.resize(c);
        for(int i = 0; i < c; i++)
        cost[i].resize(c);
        w.resize(c);
    }
    node(int c){
        cost.resize(c);
        for(int i = 0; i < c; i++)
        cost[i].resize(c);
        w.resize(c);
    }
}t[4 * nmax];

node a[nmax];
int x[nmax], y[nmax];
int ind[nmax];
node b[nmax];
node merg(node a, node b){
    node c;
    c.w = b.w;
    int n = a.w.size();
    c.cost.resize(n);
    vector <vector <int> > opt;
    opt.resize(n);
    for(int i= 0; i < n; i++)
        c.cost[i].resize(n), opt[i].resize(n);
    for(int i = 0; i < n; i++){
        int mn = 1e9 + 1, mni;
        for(int j= 0; j < n; j++){
            int val = a.cost[n - 1][j] + a.w[j] + b.cost[j][i];
            if(val < mn)
                mn = val, mni = j;
        }
        opt[n - 1][i] = mni, c.cost[n - 1][i] = mn;
    }
    for(int i = n - 2; i >= 0; i--){
        int mn = 1e9 + 1,mni;
        for(int j = 0; j < n; j++){
            int val = a.cost[i][j] + a.w[j] + b.cost[j][0];
            if(val < mn)
                mn = val, mni = j;
        }
        opt[i][0] = mni, c.cost[i][0] = mn;
        for(int j = 1; j <= n - 1; j++){
            int mn = 1e9 + 1, mni = j;
            for(int x = opt[i][j - 1]; x <= opt[i + 1][j]; x++){
                int val = a.cost[i][x] + a.w[x] + b.cost[x][j];
                if(val < mn)
                    mn = val, mni = x;
            }
            opt[i][j] = mni, c.cost[i][j] = mn;
        }
    }
    return c;
}

void update(int v, int l, int r, int pos, node a){
    if(l > pos || r < pos)
    return;
    if(l == r){
        t[v] = a;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, a);
    update(2 * v + 1, m + 1, r, pos, a);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    r = R, c = C;
    for(int i = 0; i < 5000; i++){
        for(int j = 0; j < 200; j++)
        h[i][j] = H[i][j], v[i][j] = V[i][j]; 
        a[i] = {c};
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++)
            a[i].w[j] = V[i][j];
        for(int x = 0; x < c; x++){
            a[i].cost[x][x] = 0;
            for(int y = x + 1; y < c; ++y){
                a[i].cost[x][y] = a[i].cost[x][y - 1] + H[i][y - 1];
            }
            for(int y = x - 1; y >= 0; y--)
                a[i].cost[x][y] = a[i].cost[x][y + 1] + H[i][y];
        }
    }
    for(int i= 0; i < r; i++)
    b[i] = {c};
    for(int i = 0; i < r; i++){
        if(i % 10 == 0){
            b[i / 10] = a[i];
        }
        else b[i / 10] = merg(b[i / 10], a[i]);
        s = i / 10;
    }
    for(int i = 0; i <= s; i++)
        update(1, 0, s, i, b[i]);
}

void update_block(int o){
    b[o] = a[o * 10];
    int x = o * 10;
    for(int j = x + 1; j < min(r, x + 10); j++)
        b[o] = merg(b[o], a[j]);
    update(1, 0, s, o, b[o]);
}

void changeH(int p, int q, int w) {
    /* ... */
    h[p][q] = w;
    
    for(int i = 0; i < c; i++){
        a[p].w[i] = v[p][i];
    }
    for(int x = 0; x < c; x++){
        a[p].cost[x][x] = 0;
        for(int y = x + 1; y < c; ++y){
            a[p].cost[x][y] = a[p].cost[x][y - 1] + h[p][y - 1];
        }
        for(int y = x - 1; y >= 0; y--)
            a[p].cost[x][y] = a[p].cost[x][y + 1] + h[p][y];
    }
    update_block(p / 10);
}

void changeV(int p, int q, int w) {
    /* ... */
    for(int i = 0; i < c; i++){
        a[p].w[q] = w;
    }
    update_block(p / 10);
}

int escape(int V1, int V2) {
    return t[1].cost[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 'node merg(node, node)':
wombats.cpp:64:19: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |         opt[i][0] = mni, c.cost[i][0] = mn;
wombats.cpp:55:23: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |         opt[n - 1][i] = mni, c.cost[n - 1][i] = mn;

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Runtime error 32 ms 44280 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 ms 262144 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 324 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -