Submission #776391

#	Time	Username	Problem	Language	Result	Execution time	Memory
776391		caganyanmaz	Wombats (IOI13_wombats)	C++17	39 / 100	20059 ms	34196 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24