Submission #509966

# Submission time Handle Problem Language Result Execution time Memory
509966 2022-01-14T12:49:47 Z blue Robots (APIO13_robots) C++17
0 / 100
25 ms 53068 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>;
#define sz(x) int(x.size())
 
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;
 
 
vi act_loc;
int al;
 
 
 
 
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;
 
    vi act_ind((h+2)*(w+2), -1);
 
    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;
            act_loc.push_back(i);
            act_ind[i] = sz(act_loc)-1;
 
            // 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";
 
    al = sz(act_loc);
 
 
 
    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[al];
    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[act_ind[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(al, INF);
        dp[i][i][act_ind[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(al, 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]);
            //     }
            // }
            for(int k = i; k < j; k++)
                for(int x = 0; x < al; 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 < al; 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 < al; u++)
    {
        final_ans = min(final_ans, dp[0][n-1][u]);
    }
 
    if(final_ans >= INF) final_ans = -1;
    cout << final_ans << '\n';
}
# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 53068 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 53068 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 53068 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 53068 KB Output isn't correct
2 Halted 0 ms 0 KB -