oj.uz

Submission #509954

# Submission time Handle Problem Language Result Execution time Memory
509954 2022-01-14T12:35:17 Z blue Robots (APIO13_robots) C++17
60 / 100
 236 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>;
using vvi = vector<vi>;

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

vvi edge;
vvi 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 = vvi(5*(h+2)*(w+2));
    rev_edge = vvi(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';
        }
    }

    // for(int f = )
    edge.clear();
    rev_edge.clear();

















    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';


}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 53068 KB Output is correct
2 Correct 24 ms 53104 KB Output is correct
3 Correct 25 ms 53136 KB Output is correct
4 Correct 26 ms 53212 KB Output is correct
5 Correct 25 ms 53100 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 53068 KB Output is correct
2 Correct 24 ms 53104 KB Output is correct
3 Correct 25 ms 53136 KB Output is correct
4 Correct 26 ms 53212 KB Output is correct
5 Correct 25 ms 53100 KB Output is correct
6 Correct 25 ms 53068 KB Output is correct
7 Correct 26 ms 53068 KB Output is correct
8 Correct 26 ms 53140 KB Output is correct
9 Correct 25 ms 53088 KB Output is correct
10 Correct 25 ms 53196 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 53068 KB Output is correct
2 Correct 24 ms 53104 KB Output is correct
3 Correct 25 ms 53136 KB Output is correct
4 Correct 26 ms 53212 KB Output is correct
5 Correct 25 ms 53100 KB Output is correct
6 Correct 25 ms 53068 KB Output is correct
7 Correct 26 ms 53068 KB Output is correct
8 Correct 26 ms 53140 KB Output is correct
9 Correct 25 ms 53088 KB Output is correct
10 Correct 25 ms 53196 KB Output is correct
11 Correct 172 ms 110156 KB Output is correct
12 Correct 109 ms 93528 KB Output is correct
13 Correct 135 ms 104452 KB Output is correct
14 Correct 236 ms 109520 KB Output is correct
15 Correct 164 ms 109252 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 53068 KB Output is correct
2 Correct 24 ms 53104 KB Output is correct
3 Correct 25 ms 53136 KB Output is correct
4 Correct 26 ms 53212 KB Output is correct
5 Correct 25 ms 53100 KB Output is correct
6 Correct 25 ms 53068 KB Output is correct
7 Correct 26 ms 53068 KB Output is correct
8 Correct 26 ms 53140 KB Output is correct
9 Correct 25 ms 53088 KB Output is correct
10 Correct 25 ms 53196 KB Output is correct
11 Correct 172 ms 110156 KB Output is correct
12 Correct 109 ms 93528 KB Output is correct
13 Correct 135 ms 104452 KB Output is correct
14 Correct 236 ms 109520 KB Output is correct
15 Correct 164 ms 109252 KB Output is correct
16 Runtime error 134 ms 163844 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -