oj.uz

답안 #790615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
790615 2023-07-23T00:50:07 Z Ronin13 웜뱃 (IOI13_wombats) C++17
0 / 100
 27 ms 32496 KB 
#include <bits/stdc++.h>
#include "wombats.h"
#define ll long long 
#define ull unsigned ll
#define f first
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 500;
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[3 * 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]; 
     
    }
    for(int i = 0; i < r; i++){
        node a = {c};
        for(int j = 0; j < c; j++)
            a.w[j] = V[i][j];
        for(int x = 0; x < c; x++){
            a.cost[x][x] = 0;
            for(int y = x + 1; y < c; ++y){
                a.cost[x][y] = a.cost[x][y - 1] + H[i][y - 1];
            }
            for(int y = x - 1; y >= 0; y--)
                a.cost[x][y] = a.cost[x][y + 1] + H[i][y];
        }
        if(i % 10 == 0)
            b[i / 10] = a;
        else b[i / 10] =  merg(b[i / 10], a);
        s = i / 10;
    }
    
    for(int i = 0; i <= s; i++)
        update(1, 0, s, i, b[i]);
    for(int i = 0; i <= 3 * s; i++)
        t[i] = {};
}

void update_block(int o){
   // b[o] = a[o * 10];
    int x = o * 10;
    for(int i = x; i < min(r, x + 10); i++){
        node a = {c};
        for(int j = 0; j < c; j++)
            a.w[j] = v[i][j];
        for(int x = 0; x < c; x++){
            a.cost[x][x] = 0;
            for(int y = x + 1; y < c; ++y){
                a.cost[x][y] = a.cost[x][y - 1] + h[i][y - 1];
            }
            for(int y = x - 1; y >= 0; y--)
                a.cost[x][y] = a.cost[x][y + 1] + h[i][y];
        }
        if(i % 10 == 0)
            b[i / 10] = a;
        else b[i / 10] =  merg(b[i / 10], a);
    }
    update(1, 0, s, o, b[o]);
}

void changeH(int p, int q, int w) {
    /* ... */
    h[p][q] = w;
    update_block(p / 10);
}

void changeV(int p, int q, int w) {
    /* ... */
    
    v[p][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:61:19: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |         opt[i][0] = mni, c.cost[i][0] = mn;
wombats.cpp:52:23: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |         opt[n - 1][i] = mni, c.cost[n - 1][i] = mn;

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8124 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Runtime error 12 ms 16592 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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