oj.uz

Submission #218030

# Submission time Handle Problem Language Result Execution time Memory
218030 2020-03-31T12:49:15 Z SamAnd Robots (APIO13_robots) C++17
100 / 100
 743 ms 143328 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 503, K = 9, INF = 1000000009;
const int xx[4] = {-1, 0, 1, 0};
const int yy[4] = {0, 1, 0, -1};
struct ban
{
    int x, y;
    ban(){}
    ban(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};

int n, m, k;
char a[N][N];
int sx[K], sy[K];

int c[N][N][4];
ban u[N][N][4];
void dfs(int x, int y, int z)
{
    c[x][y][z] = 1;
    int hx = x + xx[z];
    int hy = y + yy[z];
    int hz = z;
    if (!(hx >= 1 && hx <= n && hy >= 1 && hy <= m) || a[hx][hy] == 'x')
    {
        hx = x;
        hy = y;
    }
    else if (a[hx][hy] == 'C')
        hz = (z + 1) % 4;
    else if (a[hx][hy] == 'A')
        hz = (z - 1 + 4) % 4;
    if (hx == x && hy == y)
    {
        u[x][y][z] = ban(x, y);
        c[x][y][z] = 2;
        return;
    }
    if (!c[hx][hy][hz])
    {
        dfs(hx, hy, hz);
        u[x][y][z] = u[hx][hy][hz];
        c[x][y][z] = 2;
        return;
    }
    if (c[hx][hy][hz] == 2)
    {
        u[x][y][z] = u[hx][hy][hz];
        c[x][y][z] = 2;
        return;
    }
    u[x][y][z] = ban(-1, -1);
    c[x][y][z] = 2;
    return;
}

int z[K][K];
int dp[(K * (K + 1)) / 2][N][N];

bool cc[N][N];
vector<ban> q[N * N * K];

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; ++i)
        scanf(" %s", (a[i] + 1));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if ('1' <= a[i][j] && a[i][j] <= '9')
            {
                sx[a[i][j] - '1'] = i;
                sy[a[i][j] - '1'] = j;
                a[i][j] = '.';
            }
        }
    }
    for (int i0 = 0; i0 < (K * (K + 1)) / 2; ++i0)
        for (int i2 = 0; i2 < N; ++i2)
            for (int i3 = 0; i3 < N; ++i3)
                dp[i0][i2][i3] = INF;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int k = 0; k < 4; ++k)
            {
                if (!c[i][j][k])
                {
                    dfs(i, j, k);
                }
            }
        }
    }
    int zz = 0;
    for (int d = 1; d <= k; ++d)
    {
        for (int l = 0; l <= k - d; ++l)
        {
            int r = l + d - 1;
            z[l][r] = zz++;
        }
    }
    for (int d = 1; d <= k; ++d)
    {
        for (int l = 0; l <= k - d; ++l)
        {
            int r = l + d - 1;
            if (l == r)
                dp[z[l][r]][sx[l]][sy[l]] = 0;
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    for (int m = l; m < r; ++m)
                        dp[z[l][r]][i][j] = min(dp[z[l][r]][i][j], dp[z[l][m]][i][j] + dp[z[m + 1][r]][i][j]);
                }
            }
            memset(cc, false, sizeof cc);
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    if (dp[z[l][r]][i][j] != INF)
                        q[dp[z[l][r]][i][j]].push_back(ban(i, j));
                }
            }
            for (int ii = 0; ii < N * N * K; ++ii)
            {
                while (!q[ii].empty())
                {
                    ban t = q[ii].back();
                    q[ii].pop_back();
                    if (cc[t.x][t.y])
                        continue;
                    cc[t.x][t.y] = true;
                    for (int i = 0; i < 4; ++i)
                    {
                        ban h = u[t.x][t.y][i];
                        if (h.x == -1)
                            continue;
                        if (dp[z[l][r]][t.x][t.y] + 1 < dp[z[l][r]][h.x][h.y])
                        {
                            dp[z[l][r]][h.x][h.y] = dp[z[l][r]][t.x][t.y] + 1;
                            q[dp[z[l][r]][h.x][h.y]].push_back(h);
                        }
                    }
                }
            }
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            ans = min(ans, dp[z[0][k - 1]][i][j]);
        }
    }
    if (ans == INF)
        printf("-1\n");
    else
        printf("%d\n", ans);
    return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &k, &m, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", (a[i] + 1));
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 98552 KB Output is correct
2 Correct 74 ms 98552 KB Output is correct
3 Correct 75 ms 98552 KB Output is correct
4 Correct 72 ms 98680 KB Output is correct
5 Correct 81 ms 98808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 98552 KB Output is correct
2 Correct 74 ms 98552 KB Output is correct
3 Correct 75 ms 98552 KB Output is correct
4 Correct 72 ms 98680 KB Output is correct
5 Correct 81 ms 98808 KB Output is correct
6 Correct 77 ms 98560 KB Output is correct
7 Correct 81 ms 98552 KB Output is correct
8 Correct 77 ms 98680 KB Output is correct
9 Correct 74 ms 98680 KB Output is correct
10 Correct 74 ms 98680 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 98552 KB Output is correct
2 Correct 74 ms 98552 KB Output is correct
3 Correct 75 ms 98552 KB Output is correct
4 Correct 72 ms 98680 KB Output is correct
5 Correct 81 ms 98808 KB Output is correct
6 Correct 77 ms 98560 KB Output is correct
7 Correct 81 ms 98552 KB Output is correct
8 Correct 77 ms 98680 KB Output is correct
9 Correct 74 ms 98680 KB Output is correct
10 Correct 74 ms 98680 KB Output is correct
11 Correct 348 ms 109024 KB Output is correct
12 Correct 78 ms 105720 KB Output is correct
13 Correct 228 ms 105292 KB Output is correct
14 Correct 442 ms 114204 KB Output is correct
15 Correct 337 ms 106336 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 98552 KB Output is correct
2 Correct 74 ms 98552 KB Output is correct
3 Correct 75 ms 98552 KB Output is correct
4 Correct 72 ms 98680 KB Output is correct
5 Correct 81 ms 98808 KB Output is correct
6 Correct 77 ms 98560 KB Output is correct
7 Correct 81 ms 98552 KB Output is correct
8 Correct 77 ms 98680 KB Output is correct
9 Correct 74 ms 98680 KB Output is correct
10 Correct 74 ms 98680 KB Output is correct
11 Correct 348 ms 109024 KB Output is correct
12 Correct 78 ms 105720 KB Output is correct
13 Correct 228 ms 105292 KB Output is correct
14 Correct 442 ms 114204 KB Output is correct
15 Correct 337 ms 106336 KB Output is correct
16 Correct 414 ms 111000 KB Output is correct
17 Correct 743 ms 143328 KB Output is correct
18 Correct 451 ms 115184 KB Output is correct
19 Correct 394 ms 111052 KB Output is correct
20 Correct 557 ms 125968 KB Output is correct