Submission #1118920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118920		ALTAKEXE	Robots (APIO13_robots)	C++17	100 / 100	466 ms	145804 KiB

robots

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define INF INT_MAX
#define FOR(i, b) for (int i = 0; i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int MOD = 1e9 + 7;
using namespace std;
// using hasing, O(W*H*N^3);
const int MV = 502 * 502;
const int ME = 502 * 502 * 4 * 2;
struct point
{
        point() {}
        point(int x, int y) : x(x), y(y) {}
        int x, y;
        int value() { return 500 * (x - 1) + y; }
} inp[10];
int n, w, h;
int xx[4] = {-1, 0, 1, 0}, yy[4] = {0, 1, 0, -1};
char ch[510][510];
bool wall[510][510];
bool m_check[4][510][510]; // using in function make_edge;
bool A[510][510], C[510][510];
bool check[MV];    // using in function Merge;
int Q[MV][2];      // 0:depth, 1:tr of point;
short b_check[MV]; // using in function BFS;	assigned by 1~9;
int Dp[9][9][502][502];

typedef pair<int, int> P;
vector<point> has;
int st[MV], en[ME];
int nxt[ME];
int c_edge;
vector<int> Hash[2500020];

inline int tr(int x, int y) { return 500 * (x - 1) + y; }
P itr(int x) { return P((x - 1) / 500 + 1, (x - 1) % 500 + 1); }
void addedge(int s, int d)
{
        ++c_edge;
        nxt[c_edge] = st[s];
        st[s] = c_edge;
        en[c_edge] = d;
}

void make_edge()
{
        int i, j, k;
        for (i = 1; i <= h; i++)
        {
                for (j = 1; j <= w; j++)
                {
                        for (k = 0; k < 4; k++)
                        {
                                if (wall[i + xx[k ^ 2]][j + yy[k ^ 2]])
                                        continue;
                                int ink = k;
                                int tx = i, ty = j;
                                if (A[i][j])
                                        ink = (ink + 1) % 4;
                                else if (C[i][j])
                                        ink = (ink ? ink - 1 : 3);
                                while (!m_check[ink][tx][ty] && wall[tx][ty])
                                {
                                        // printf("%d %d -> %d %d\n",tx,ty,i,j);
                                        addedge(tr(tx, ty), tr(i, j));
                                        m_check[ink][tx][ty] = 1;
                                        tx += xx[ink];
                                        ty += yy[ink];
                                        if (A[tx][ty])
                                                ink = (ink + 1) % 4;
                                        else if (C[tx][ty])
                                                ink = (ink ? ink - 1 : 3);
                                }
                        }
                }
        }
}

void BFS(int x)
{
        int fr = 1, re = 0;
        int vx = inp[x].value();
        Q[0][0] = vx, Q[0][1] = 0;
        b_check[vx] = x + 1;
        while (fr != re)
        {
                int i;
                int tx = Q[re][0];
                for (i = st[tx]; i; i = nxt[i])
                {
                        if (b_check[en[i]] == x + 1)
                                continue;
                        b_check[en[i]] = x + 1;
                        Q[fr][0] = en[i];
                        Q[fr][1] = Q[re][1] + 1;
                        fr++;
                }
                P tmp = itr(Q[re][0]);
                Dp[x][x][tmp.first][tmp.second] = Q[re++][1];
        }
}

void Init()
{
        int i, j, k;
        for (i = 0; i < n; i++)
        {
                for (j = 1; j <= h; j++)
                {
                        for (k = 1; k <= w; k++)
                        {
                                if (inp[i].x == j && inp[i].y == k)
                                        continue;
                                if (!Dp[i][i][j][k])
                                        Dp[i][i][j][k] = INF;
                        }
                }
        }
}

void Merge(int a, int b, int c)
{
        // assigning Dp[a][c] with Dp[a][b] & Dp[b+1][c];
        memset(check, 0, sizeof(check));
        int max_num = 0;
        int i, j;
        for (i = 1; i <= h; i++)
        {
                for (j = 1; j <= w; j++)
                {
                        if (Dp[a][b][i][j] == INF || Dp[b + 1][c][i][j] == INF)
                                continue;
                        int tmp = tr(i, j);
                        int tmp2 = Dp[a][b][i][j] + Dp[b + 1][c][i][j];
                        Hash[tmp2].push_back(tmp);
                        max_num = max(max_num, tmp2);
                }
        }
        for (i = 1; i <= max_num; i++)
        {
                if (Hash[i].empty())
                        continue;
                for (j = 0; j < Hash[i].size(); j++)
                {
                        if (check[Hash[i][j]])
                                continue;
                        check[Hash[i][j]] = 1;
                        P tmp = itr(Hash[i][j]);
                        Dp[a][c][tmp.first][tmp.second] = min(Dp[a][c][tmp.first][tmp.second], i);
                        for (int k = st[Hash[i][j]]; k; k = nxt[k])
                        {
                                if (check[en[k]])
                                        continue;
                                Hash[i + 1].push_back(en[k]);
                                max_num = max(max_num, i + 1);
                        }
                }
                Hash[i].clear();
        }
}

void output()
{
        int i, j, ans = INF;
        for (i = 1; i <= h; i++)
        {
                for (j = 1; j <= w; j++)
                {
                        ans = min(ans, Dp[0][n - 1][i][j]);
                }
        }
        printf("%d", ans == INF ? -1 : ans);
}

void init(int x, int y)
{
        int i, j;
        for (i = 1; i <= h; i++)
        {
                for (j = 1; j <= w; j++)
                        Dp[x][y][i][j] = INF;
        }
}

int main()
{
        //	freopen("input.txt","r",stdin);
        scanf("%d%d%d", &n, &w, &h);
        int i, j, k;
        for (i = 1; i <= h; i++)
        {
                scanf("%s", ch[i] + 1);
                for (j = 1; j <= w; j++)
                {
                        if (ch[i][j] != 'x')
                                wall[i][j] = 1;
                        if (ch[i][j] <= '9' && ch[i][j] >= '1')
                                inp[ch[i][j] - '1'] = point(i, j);
                        if (ch[i][j] == 'A')
                                A[i][j] = 1;
                        else if (ch[i][j] == 'C')
                                C[i][j] = 1;
                }
        }
        make_edge();
        for (i = 0; i < n; i++)
                BFS(i);
        Init();
        for (i = 1; i < n; i++)
        {
                for (j = 0; j < n - i; j++)
                {
                        // assigning Dp[j][j+i];
                        init(j, j + i);
                        for (k = 0; k < i; k++)
                        {
                                // Dp[j][j+i] = Dp[j][j+k]+Dp[j+k+1][j+i];
                                Merge(j, j + k, j + i);
                        }
                }
        }
        output();
        return 0;
}

Compilation message (stderr)

robots.cpp: In function 'void Merge(int, int, int)':
robots.cpp:147:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |                 for (j = 0; j < Hash[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |         scanf("%d%d%d", &n, &w, &h);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:196:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |                 scanf("%s", ch[i] + 1);
      |                 ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40