oj.uz

Submission #776391

# Submission time Handle Problem Language Result Execution time Memory
776391 2023-07-07T19:42:36 Z caganyanmaz Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 34196 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*C);
        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 13 ms 28088 KB Output is correct
2 Correct 13 ms 28184 KB Output is correct
3 Correct 67 ms 29784 KB Output is correct
4 Correct 13 ms 28204 KB Output is correct
5 Correct 12 ms 28116 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 56 ms 1536 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12013 ms 1464 KB Output is correct
2 Correct 18783 ms 1828 KB Output is correct
3 Correct 12135 ms 1464 KB Output is correct
4 Correct 12201 ms 1456 KB Output is correct
5 Correct 12228 ms 1620 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Execution timed out 20006 ms 1536 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 32084 KB Output is correct
2 Correct 30 ms 31968 KB Output is correct
3 Correct 24 ms 32044 KB Output is correct
4 Correct 51 ms 32876 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12206 ms 1464 KB Output is correct
2 Correct 18752 ms 1776 KB Output is correct
3 Correct 12170 ms 1468 KB Output is correct
4 Correct 12078 ms 1468 KB Output is correct
5 Correct 12024 ms 1616 KB Output is correct
6 Correct 27 ms 32084 KB Output is correct
7 Correct 32 ms 32080 KB Output is correct
8 Correct 25 ms 32096 KB Output is correct
9 Correct 51 ms 32848 KB Output is correct
10 Correct 13 ms 28116 KB Output is correct
11 Correct 13 ms 28128 KB Output is correct
12 Correct 68 ms 29772 KB Output is correct
13 Correct 14 ms 28116 KB Output is correct
14 Correct 13 ms 28196 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 57 ms 1612 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Execution timed out 20059 ms 1528 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12107 ms 1544 KB Output is correct
2 Correct 18933 ms 1892 KB Output is correct
3 Correct 12148 ms 1460 KB Output is correct
4 Correct 12359 ms 1536 KB Output is correct
5 Correct 12120 ms 1692 KB Output is correct
6 Correct 23 ms 32028 KB Output is correct
7 Correct 31 ms 32096 KB Output is correct
8 Correct 25 ms 32084 KB Output is correct
9 Correct 51 ms 32792 KB Output is correct
10 Correct 14 ms 28116 KB Output is correct
11 Correct 16 ms 28116 KB Output is correct
12 Correct 68 ms 29784 KB Output is correct
13 Correct 16 ms 28084 KB Output is correct
14 Correct 13 ms 28088 KB Output is correct
15 Execution timed out 20057 ms 34196 KB Time limit exceeded
16 Halted 0 ms 0 KB -