oj.uz

Submission #509950

# Submission time Handle Problem Language Result Execution time Memory
509950 2022-01-14T12:32:04 Z blue Robots (APIO13_robots) C++17
60 / 100
 205 ms 163844 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;

const int fr = 0;
const int lt = 3;
const int rt = 1;
const int bl = 2;

int n, h, w;

int mov[5];

// const int tm

vi* edge;
vi* rev_edge;

void add_edge(int u, int v)
{
    edge[u].push_back(v);
    rev_edge[v].push_back(u);
}





const int INF = 10'000'000;

vi occ[500*500*9];
vi* act_edge;

void bfs(vi& dst, int mxd)
{
    // cerr <<"bfs called\n";
    bool flg = (mxd==0);
    queue<int> tbv;
    for(int d = 0; d <= mxd; d++)
    {
        // cerr << "d = " << d << ", mxd = " << mxd << '\n';
        for(int o: occ[d])
        {
            // cerr << "o = " << o << '\n';
            if(dst[o] != d) continue;
            tbv.push(o);
        }
        // cerr << "chk\n";

        while((!tbv.empty()) && dst[tbv.front()] == d)
        {
            int u = tbv.front();
            tbv.pop();

            for(int v: act_edge[u])
            {
                if(dst[v] <= dst[u] + 1) continue;
                dst[v] = dst[u] + 1;
                tbv.push(v);
                mxd = max(mxd, dst[v]);
            }
        }
    }
}









int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> w >> h;

    vi state((h+2)*(w+2), bl);

    int loc[n];

    for(int r = 1; r <= h; r++)
    {
        for(int c = 1; c <= w; c++)
        {
            int i = (w+2)*r+c;

            char z;
            cin >> z;

            if('1' <= z && z <= '9')
            {
                loc[z-'1'] = i;
                state[i] = fr;
            }
            else if(z == '.')
            {
                state[i] = fr;
            }
            else if(z == 'A')
            {
                state[i] = lt;
            }
            else if(z == 'C')
            {
                state[i] = rt;
            }
            else if(z == 'x')
            {
                state[i] = bl;
            }
        }
    }

    mov[0] = -(w+2); //0 = top
    mov[1] = +1; //1 = right
    mov[2] = +(w+2); //2 = down
    mov[3] = -1; //3 = left
    mov[4] = 0;

    // vi edge[5*(h+2)*(w+2)];
    // vi in_edgd
    edge = new vi[5*(h+2)*(w+2)];
    rev_edge = new vi[5*(h+2)*(w+2)];

    vi dest(5*(h+2)*(w+2), -1);
    queue<int> tbv;

    for(int r = 1; r <= h; r++)
    {
        for(int c = 1; c <= w; c++)
        {
            int i = (w+2)*r + c;

            if(state[i] == bl) continue;

            // cerr << r << ' ' << c << '\n';

            for(int dir = 0; dir <= 3; dir++)
            {
                // cerr << "   " << dir << '\n';
                add_edge(5*i + 4, 5*i + dir);
                // cerr << "A\n";
                if(state[i + mov[dir]] != bl)
                {
                    // cerr << "B\n";
                    add_edge(5*i + dir, 5*(i + mov[dir]) + (dir + state[i + mov[dir]])%4);
                    // cerr << "C\n";
                }
                else
                {
                    // cerr << "D\n";
                    add_edge(5*i + dir, 5*i + 4);
                    dest[5*i + dir] = i;
                    tbv.push(5*i + dir);
                    // cerr << "E\n";
                }
            }
        }
    }
    // cerr << "A\n";



    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();
        for(int v: rev_edge[u])
        {
            if(v % 5 == 4) continue;
            if(dest[v] != -1) continue;
            dest[v] = dest[u];
            tbv.push(v);
        }
    }


    act_edge = new vi[(h+2)*(w+2)];
    for(int r = 1; r <= h; r++)
    {
        for(int c = 1; c <= w; c++)
        {
            int ind = (w+2)*r + c;

            for(int q = 0; q < 4; q++)
            {
                if(dest[5*ind + q] ==  -1 || dest[5*ind+q] == ind) continue;
                act_edge[ind].push_back(dest[5*ind+q]);
            }

            // cerr << "current cell = " << r << ' ' << c << " : ";
            // for(int a: act_edge[ind]) cerr << a/(w+2) << " " << a%(w+2) << " | ";
            // cerr << '\n';
        }
    }



















    vi dp[n][n];
    for(int i = 0; i < n; i++)
    {
        occ[0].push_back(loc[i]);
        dp[i][i] = vi((h+2)*(w+2), INF);
        dp[i][i][loc[i]] = 0;
        bfs(dp[i][i], 0);
        occ[0].pop_back();

        // cerr << "\n\n\n";
        // cerr << "robot = " << i+1 << '\n';
        // for(int l = 0; l < (h+2)*(w+2); l++)
        // {
        //     if(dp[i][i][l] >= INF) continue;
        //     // cerr << l/(w+2) << ' ' << l%(w+2) << " : " << dp[i][i][l] << '\n';
        // }
    }

    for(int d = 1; d < n; d++)
    {
        for(int i = 0; i+d < n; i++)
        {
            int j = i+d;
            // cerr << "\n\n\n computing dp " << i << ' ' << j << '\n';

            dp[i][j] = vi((h+2)*(w+2), INF);

            for(int k = i; k < j; k++)
            {
                for(int x = 0; x < (h+2)*(w+2); x++)
                {
                    dp[i][j][x] = min(dp[i][j][x], dp[i][k][x] + dp[k+1][j][x]);
                }
            }

            vi elim;

            for(int u = 0; u < (h+2)*(w+2); u++)
                if(dp[i][j][u] < INF) //add constraint on bfs here?
                {
                    occ[dp[i][j][u]].push_back(u);
                    elim.push_back(dp[i][j][u]);
                }

            bfs(dp[i][j], d*h*w);

            for(int e: elim) occ[e].clear();
        }
    }

    int final_ans = INF;

    for(int u = 0; u < (h+2)*(w+2); u++)
    {
        final_ans = min(final_ans, dp[0][n-1][u]);
    }

    if(final_ans >= INF) final_ans = -1;
    cout << final_ans << '\n';


}

Compilation message

robots.cpp: In function 'void bfs(vi&, int)':
robots.cpp:45:10: warning: unused variable 'flg' [-Wunused-variable]
   45 |     bool flg = (mxd==0);
      |          ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 53068 KB Output is correct
2 Correct 28 ms 53080 KB Output is correct
3 Correct 25 ms 53060 KB Output is correct
4 Correct 25 ms 53144 KB Output is correct
5 Correct 30 ms 53156 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 53068 KB Output is correct
2 Correct 28 ms 53080 KB Output is correct
3 Correct 25 ms 53060 KB Output is correct
4 Correct 25 ms 53144 KB Output is correct
5 Correct 30 ms 53156 KB Output is correct
6 Correct 25 ms 53136 KB Output is correct
7 Correct 26 ms 53068 KB Output is correct
8 Correct 27 ms 53100 KB Output is correct
9 Correct 26 ms 53140 KB Output is correct
10 Correct 26 ms 53152 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 53068 KB Output is correct
2 Correct 28 ms 53080 KB Output is correct
3 Correct 25 ms 53060 KB Output is correct
4 Correct 25 ms 53144 KB Output is correct
5 Correct 30 ms 53156 KB Output is correct
6 Correct 25 ms 53136 KB Output is correct
7 Correct 26 ms 53068 KB Output is correct
8 Correct 27 ms 53100 KB Output is correct
9 Correct 26 ms 53140 KB Output is correct
10 Correct 26 ms 53152 KB Output is correct
11 Correct 151 ms 111796 KB Output is correct
12 Correct 73 ms 93656 KB Output is correct
13 Correct 102 ms 104608 KB Output is correct
14 Correct 205 ms 112908 KB Output is correct
15 Correct 144 ms 110112 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 53068 KB Output is correct
2 Correct 28 ms 53080 KB Output is correct
3 Correct 25 ms 53060 KB Output is correct
4 Correct 25 ms 53144 KB Output is correct
5 Correct 30 ms 53156 KB Output is correct
6 Correct 25 ms 53136 KB Output is correct
7 Correct 26 ms 53068 KB Output is correct
8 Correct 27 ms 53100 KB Output is correct
9 Correct 26 ms 53140 KB Output is correct
10 Correct 26 ms 53152 KB Output is correct
11 Correct 151 ms 111796 KB Output is correct
12 Correct 73 ms 93656 KB Output is correct
13 Correct 102 ms 104608 KB Output is correct
14 Correct 205 ms 112908 KB Output is correct
15 Correct 144 ms 110112 KB Output is correct
16 Runtime error 143 ms 163844 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -