oj.uz

Submission #776389

# Submission time Handle Problem Language Result Execution time Memory
776389 2023-07-07T19:36:06 Z caganyanmaz Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 43616 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 12 ms 28116 KB Output is correct
2 Correct 12 ms 28116 KB Output is correct
3 Correct 65 ms 29692 KB Output is correct
4 Correct 12 ms 28116 KB Output is correct
5 Correct 12 ms 28184 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 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 468 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 504 KB Output is correct
11 Correct 65 ms 1500 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 12181 ms 1464 KB Output is correct
2 Correct 18962 ms 1856 KB Output is correct
3 Correct 12157 ms 1544 KB Output is correct
4 Correct 12191 ms 1544 KB Output is correct
5 Correct 12116 ms 1696 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 384 KB Output is correct
9 Execution timed out 20075 ms 1492 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32084 KB Output is correct
2 Correct 29 ms 32060 KB Output is correct
3 Correct 22 ms 32056 KB Output is correct
4 Correct 51 ms 33460 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12233 ms 1552 KB Output is correct
2 Correct 18798 ms 1976 KB Output is correct
3 Correct 12172 ms 1548 KB Output is correct
4 Correct 12051 ms 1544 KB Output is correct
5 Correct 12306 ms 1696 KB Output is correct
6 Correct 27 ms 32084 KB Output is correct
7 Correct 28 ms 32076 KB Output is correct
8 Correct 22 ms 32156 KB Output is correct
9 Correct 57 ms 33444 KB Output is correct
10 Correct 14 ms 28116 KB Output is correct
11 Correct 13 ms 28160 KB Output is correct
12 Correct 68 ms 30932 KB Output is correct
13 Correct 12 ms 28244 KB Output is correct
14 Correct 12 ms 28228 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 312 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 596 KB Output is correct
22 Correct 1 ms 440 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 56 ms 2892 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Execution timed out 20014 ms 1728 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12083 ms 1536 KB Output is correct
2 Correct 19054 ms 1952 KB Output is correct
3 Correct 12002 ms 1540 KB Output is correct
4 Correct 12027 ms 1548 KB Output is correct
5 Correct 11972 ms 1692 KB Output is correct
6 Correct 24 ms 32084 KB Output is correct
7 Correct 29 ms 32140 KB Output is correct
8 Correct 22 ms 32160 KB Output is correct
9 Correct 59 ms 33516 KB Output is correct
10 Correct 14 ms 28188 KB Output is correct
11 Correct 12 ms 28228 KB Output is correct
12 Correct 70 ms 30960 KB Output is correct
13 Correct 12 ms 28208 KB Output is correct
14 Correct 12 ms 28116 KB Output is correct
15 Execution timed out 20057 ms 43616 KB Time limit exceeded
16 Halted 0 ms 0 KB -