oj.uz

Submission #509955

# Submission time Handle Problem Language Result Execution time Memory
509955 2022-01-14T12:39:19 Z blue Robots (APIO13_robots) C++17
60 / 100
 241 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();
    dest.clear();
    state.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 23 ms 53068 KB Output is correct
2 Correct 27 ms 53092 KB Output is correct
3 Correct 30 ms 53084 KB Output is correct
4 Correct 26 ms 53192 KB Output is correct
5 Correct 26 ms 53116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53068 KB Output is correct
2 Correct 27 ms 53092 KB Output is correct
3 Correct 30 ms 53084 KB Output is correct
4 Correct 26 ms 53192 KB Output is correct
5 Correct 26 ms 53116 KB Output is correct
6 Correct 25 ms 53152 KB Output is correct
7 Correct 28 ms 53068 KB Output is correct
8 Correct 24 ms 53068 KB Output is correct
9 Correct 28 ms 53164 KB Output is correct
10 Correct 26 ms 53160 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53068 KB Output is correct
2 Correct 27 ms 53092 KB Output is correct
3 Correct 30 ms 53084 KB Output is correct
4 Correct 26 ms 53192 KB Output is correct
5 Correct 26 ms 53116 KB Output is correct
6 Correct 25 ms 53152 KB Output is correct
7 Correct 28 ms 53068 KB Output is correct
8 Correct 24 ms 53068 KB Output is correct
9 Correct 28 ms 53164 KB Output is correct
10 Correct 26 ms 53160 KB Output is correct
11 Correct 167 ms 110072 KB Output is correct
12 Correct 97 ms 93576 KB Output is correct
13 Correct 112 ms 104480 KB Output is correct
14 Correct 241 ms 109484 KB Output is correct
15 Correct 151 ms 109332 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53068 KB Output is correct
2 Correct 27 ms 53092 KB Output is correct
3 Correct 30 ms 53084 KB Output is correct
4 Correct 26 ms 53192 KB Output is correct
5 Correct 26 ms 53116 KB Output is correct
6 Correct 25 ms 53152 KB Output is correct
7 Correct 28 ms 53068 KB Output is correct
8 Correct 24 ms 53068 KB Output is correct
9 Correct 28 ms 53164 KB Output is correct
10 Correct 26 ms 53160 KB Output is correct
11 Correct 167 ms 110072 KB Output is correct
12 Correct 97 ms 93576 KB Output is correct
13 Correct 112 ms 104480 KB Output is correct
14 Correct 241 ms 109484 KB Output is correct
15 Correct 151 ms 109332 KB Output is correct
16 Runtime error 150 ms 163844 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -