oj.uz

Submission #776393

# Submission time Handle Problem Language Result Execution time Memory
776393 2023-07-07T19:46:20 Z caganyanmaz Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 55072 KB 
#include <bits/stdc++.h>
#include "wombats.h"
#define int int64_t
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cout << (#x) << ": " << (x) <<"\n"
#else
#define debug(x)
#endif

constexpr static int MXR = 5000;
constexpr static int MXSQR = 80;
constexpr static int MXC = 200;
constexpr static int INF = 1e18;

int r, c, sqr, sqr_size;
int ways[MXSQR][MXC][MXC];
int complete_ways[MXC][MXC];
int min_dist[MXR][MXC];
int h[MXR][MXC];
int v[MXR][MXC];
int tmp[MXC][MXC];

bitset<MXC> visited[MXR];

int add(int a, int b)
{
        if (INF - a < b) return INF;
        return a + b;
}

void merge_sections()
{
        for (int i = 0; i < c; i++)
                for (int j = 0; j < c; j++)
                        complete_ways[i][j] = (i==j) ? 0 : INF;
        for (int i = 0; i < sqr; i++) // C^3 :(
        {
                for (int j = 0; j < c; j++)
                        for (int k = 0; k < c; k++)
                                tmp[j][k] = INF;
                for (int j = 0; j < c; j++)
                        for (int k = 0; k < c; k++)
                                for (int l = 0; l < c; l++)
                                        tmp[j][k] = min(tmp[j][k], add(complete_ways[j][l], ways[i][l][k]));
                for (int j = 0; j < c; j++)
                        for (int k = 0; k < c; k++)
                                complete_ways[j][k] = tmp[j][k];
        }
}

void calculate_section(int x)
{
        int ss = x*sqr_size, ee = min((x+1)*sqr_size, r-1);
        for (int root = 0; root < c; root++)
        {
                for (int k = ss; k <= ee; k++)
                {
                        for (int l = 0; l < c; l++)
                        {
                                min_dist[k][l] = INF;
                                visited[k][l] = false;
                        }
                }
                priority_queue<array<int, 3>> pq;
                min_dist[ss][root] = 0;
                pq.push({0, ss, root});
                while (pq.size())
                {
                        auto [_, i, j] = pq.top();
                        pq.pop();
                        if (visited[i][j])
                                continue;
                        visited[i][j] = true;
                        if (i == ee)
                                ways[x][root][j] = min_dist[i][j];
                        if (j > 0 && min_dist[i][j] + h[i][j-1] < min_dist[i][j-1])
                        {
                                min_dist[i][j-1] = min_dist[i][j] + h[i][j-1];
                                pq.push({-min_dist[i][j-1], i, j-1});
                        }
                        if (j < c-1 && min_dist[i][j] + h[i][j] < min_dist[i][j+1])
                        {
                                min_dist[i][j+1] = min_dist[i][j] + h[i][j];
                                pq.push({-min_dist[i][j+1], i, j+1});
                        }
                        if (i < ee && min_dist[i][j] + v[i][j] < min_dist[i+1][j])
                        {
                                min_dist[i+1][j] = min_dist[i][j] + v[i][j];
                                pq.push({-min_dist[i+1][j], i+1, j});
                        }
                }
        }
}

void init(int32_t R, int32_t C, int32_t H[5000][200], int32_t V[5000][200])
{
        r = R;
        c = C;
        sqr_size = (int)sqrt((double)R);
        sqr = R / sqr_size;
        if (R % sqr_size)
                sqr++;
        for (int i = 0; i < R; i++)
        {
                for (int j = 0; j < C; j++)
                {
                        h[i][j] = H[i][j];
                        v[i][j] = V[i][j];
                }
        }
        for (int i = 0; i < sqr; i++)
                calculate_section(i);
        merge_sections();
}

void changeH(int32_t p, int32_t q, int32_t w)
{
        h[p][q] = w;
        calculate_section(p/sqr_size);
        if (!(p%sqr_size) && p != 0)
                calculate_section((p/sqr_size)-1);
        merge_sections();
}
void changeV(int32_t p, int32_t q, int32_t w)
{
        v[p][q] = w;
        calculate_section(p/sqr_size);
        merge_sections();
}

int32_t escape(int32_t V1, int32_t V2)
{
        return complete_ways[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

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28220 KB Output is correct
2 Correct 14 ms 28244 KB Output is correct
3 Correct 68 ms 29828 KB Output is correct
4 Correct 14 ms 28244 KB Output is correct
5 Correct 17 ms 28192 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 55 ms 1752 KB Output is correct
12 Correct 2 ms 696 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2150 ms 3128 KB Output is correct
2 Correct 2882 ms 3128 KB Output is correct
3 Correct 2162 ms 2932 KB Output is correct
4 Correct 2230 ms 2964 KB Output is correct
5 Correct 2117 ms 2820 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 14627 ms 3004 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32212 KB Output is correct
2 Correct 25 ms 32212 KB Output is correct
3 Correct 22 ms 32212 KB Output is correct
4 Correct 66 ms 33100 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2095 ms 3244 KB Output is correct
2 Correct 2869 ms 3132 KB Output is correct
3 Correct 2168 ms 2964 KB Output is correct
4 Correct 2075 ms 2964 KB Output is correct
5 Correct 2097 ms 3020 KB Output is correct
6 Correct 21 ms 32212 KB Output is correct
7 Correct 25 ms 32192 KB Output is correct
8 Correct 22 ms 32208 KB Output is correct
9 Correct 50 ms 33032 KB Output is correct
10 Correct 14 ms 28116 KB Output is correct
11 Correct 14 ms 28176 KB Output is correct
12 Correct 70 ms 29900 KB Output is correct
13 Correct 13 ms 28244 KB Output is correct
14 Correct 13 ms 28140 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 692 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 2 ms 696 KB Output is correct
22 Correct 1 ms 700 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 1 ms 692 KB Output is correct
25 Correct 56 ms 1736 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 14435 ms 3000 KB Output is correct
28 Execution timed out 20053 ms 43880 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2067 ms 3040 KB Output is correct
2 Correct 2841 ms 3064 KB Output is correct
3 Correct 2153 ms 2888 KB Output is correct
4 Correct 2064 ms 2880 KB Output is correct
5 Correct 2065 ms 2848 KB Output is correct
6 Correct 23 ms 32212 KB Output is correct
7 Correct 27 ms 32212 KB Output is correct
8 Correct 23 ms 32212 KB Output is correct
9 Correct 50 ms 32996 KB Output is correct
10 Correct 14 ms 28116 KB Output is correct
11 Correct 13 ms 28116 KB Output is correct
12 Correct 67 ms 29736 KB Output is correct
13 Correct 14 ms 28116 KB Output is correct
14 Correct 13 ms 28208 KB Output is correct
15 Execution timed out 20068 ms 55072 KB Time limit exceeded
16 Halted 0 ms 0 KB -