Submission #343234

#	Time	Username	Problem	Language	Result	Execution time	Memory
343234		blue	Portals (BOI14_portals)	C++11	100 / 100	859 ms	198960 KiB

portals

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

int R;
int C;
vector<int> edge[1002*1002];
vector<int> dist[1002*1002];
vector<int> blocked(1002*1002, 1);

vector<int> go_up(1002*1002, -1);
vector<int> go_down(1002*1002, -1);
vector<int> go_left(1002*1002, -1);
vector<int> go_right(1002*1002, -1);


vector<int> min_dist(1002*1002, 1e9);
vector<int> visit(1002*1002, 0);

int start;
int cake;

int u, v, w;

int pos(int r, int c)
{
    return (C+2)*r + c;
}

int pair_dist(int x, int y)
{
    return abs( (x % (C+2)) - (y % (C+2)) )  +  abs( (x / (C+2)) - (y / (C+2)) );
}







int main()
{
//Input
    cin >> R >> C;

    char c;

    for(int i = 1; i <= R; i++)
    {
        for(int j = 1; j <= C; j++)
        {
            cin >> c;
            if(c == '#') continue;

            blocked[pos(i, j)] = 0;

            if(c == 'S') start = pos(i, j);
            else if(c == 'C') cake = pos(i, j);
        }
    }





    for(int i = 0; i < 1002*1002; i++)
    {
        go_up[i] = go_left[i] = go_down[i] = go_right[i] = i;
    }






    for(int i = 0; i < 1002*1002; i++)
    {
        if(blocked[i]) continue;
        go_up[i] = go_up[i - (C+2)];
        go_left[i] = go_left[i-1];
    }

    for(int i = 1002*1002 - 1; i >= 0; i--)
    {
        if(blocked[i]) continue;
        go_down[i] = go_down[i + (C+2)];
        go_right[i] = go_right[i+1];
    }






    for(int i = 1; i <= R; i++)
    {
        for(int j = 1; j <= C; j++)
        {
            u = pos(i, j); //try swapping the two blocks of code.
            if(blocked[u]) continue;

            for(int v: {u-1, u+1, u-(C+2), u+(C+2)})
            {
                if(blocked[v]) continue;
                edge[u].push_back(v);
                dist[u].push_back(1);
            }



            w = 1e9;
            for(int q: {go_left[u], go_right[u], go_up[u], go_down[u]})
            {
                w = min(w, pair_dist(u, q) - 1);
            }

            for(int q: {go_left[u] + 1, go_right[u] - 1, go_up[u] + (C+2), go_down[u] - (C+2)} )
            {
                if(pair_dist(u, q) > w+1)
                {
                    edge[u].push_back(q);
                    dist[u].push_back(w+1);
                }
            }

            // cout << "u: " << u << '\n';
            // for(int g = 0; g < edge[u].size(); g++)
            // {
            //     cout << edge[u][g] << ' ' << dist[u][g] << '\n';
            // }
            // cout << "________________________________\n";
        }
    }









    min_dist[start] = 0;

    vector<int> dist_pos[R*C];
    dist_pos[0].push_back(start);

    for(int i = 0; i < R*C; i++)
    {
        for(int u: dist_pos[i])
        {
            if(visit[u]) continue;
            visit[u] = 1;

            for(int j = 0; j < edge[u].size(); j++)
            {
                v = edge[u][j];
                w = dist[u][j];

                if(min_dist[v] > min_dist[u] + w && R*C > min_dist[u] + w)
                {
                    min_dist[v] = min_dist[u] + w;
                    dist_pos[ min_dist[v] ].push_back(v);
                }
            }
        }
    }

    cout << min_dist[cake] << '\n';
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:157:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             for(int j = 0; j < edge[u].size(); j++)
      |                            ~~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30