oj.uz

Submission #156753

# Submission time Handle Problem Language Result Execution time Memory
156753 2019-10-07T09:11:02 Z Alexa2001 Wombats (IOI13_wombats) C++17
28 / 100
 2730 ms 16376 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int B = 500, Cmax = 205, Rmax = 5005;
const int inf = 1e9;

int N, M, rm;
int h[Rmax][Cmax], v[Rmax][Cmax];


static void min_to(int &x, int y) { if(x > y) x = y ;}

static void rec(int a[], int p)
{
    int i;
    for(i=1; i<M; ++i)
        min_to(a[i], a[i-1] + h[p][i-1]);

    for(i=M-2; i>=0; --i)
        min_to(a[i], a[i+1] + h[p][i]);
}

struct matrix
{
    int a[Cmax][Cmax];

    void combine(matrix &A, matrix &B, int pos)
    {
        int i, j, k;

        for(i=0; i<M; ++i)
            for(j=0; j<M; ++j)
            {
                a[i][j] = inf;
                for(k=0; k<M; ++k)
                    min_to(a[i][j], A.a[i][k] + B.a[k][j] + v[pos][k]);
            }
    }

    void refresh(int bucket)
    {
        int i, j, k;

        for(i=0; i<M; ++i)
        {
            for(j=0; j<M; ++j)
                a[i][j] = (i==j ? 0 : inf);

            for(k = bucket * B; k + 1 < (bucket+1) * B && k + 1 < N; ++k)
            {
                rec(a[i], k);

                for(j=0; j<M; ++j)
                    a[i][j] += v[k][j];
            }

            rec(a[i], k);
        }
    }
};


#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)


    matrix a[ (Rmax / B + 1) << 2];

    void update(int node, int st, int dr, int pos)
    {
        if(st == dr)
        {
            a[node].refresh(st);
            return;
        }

        if(pos <= mid) update(left_son, st, mid, pos);
            else update(right_son, mid+1, dr, pos);

        a[node].combine(a[left_son], a[right_son], mid);
    }

    void build(int node, int st, int dr)
    {
        if(st == dr)
        {
            a[node].refresh(st);
            return;
        }

        build(left_son, st, mid);
        build(right_son, mid+1, dr);

        a[node].combine(a[left_son], a[right_son], mid);
    }

    int get_answer(int start, int finish)
    {
        return a[1].a[start][finish];
    }



void init(int R, int C, int H[5000][200], int V[5000][200])
{
    N = R; M = C;
    rm = (N-1) / B;

    int i, j;
    for(i=0; i<N; ++i)
        for(j=0; j<M; ++j)
            h[i][j] = H[i][j], v[i][j] = V[i][j];

    build(1, 0, rm);
}

void changeH(int P, int Q, int W)
{
    h[P][Q] = W;
    update(1, 0, rm, P / B);
}

void changeV(int P, int Q, int W)
{
    v[P][Q] = W;
    update(1, 0, rm, P / B);
}

int escape(int V1, int V2)
{
    return get_answer(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]
  int res;
      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12536 KB Output is correct
2 Incorrect 14 ms 12408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 80 ms 2936 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 1000 KB Output is correct
2 Correct 451 ms 852 KB Output is correct
3 Correct 879 ms 972 KB Output is correct
4 Correct 863 ms 864 KB Output is correct
5 Correct 867 ms 888 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 404 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2730 ms 872 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 1016 KB Output is correct
2 Correct 452 ms 888 KB Output is correct
3 Correct 880 ms 888 KB Output is correct
4 Correct 860 ms 908 KB Output is correct
5 Correct 856 ms 888 KB Output is correct
6 Incorrect 22 ms 16376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 896 KB Output is correct
2 Correct 453 ms 988 KB Output is correct
3 Correct 890 ms 888 KB Output is correct
4 Correct 866 ms 888 KB Output is correct
5 Correct 857 ms 900 KB Output is correct
6 Incorrect 22 ms 16376 KB Output isn't correct
7 Halted 0 ms 0 KB -