Submission #343217

#	Time	Username	Problem	Language	Result	Execution time	Memory
343217		blue	Portals (BOI14_portals)	C++11	70 / 100	1098 ms	158812 KiB

portals

#include <iostream>
#include <vector>
#include <set>
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);

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)) );
}







struct distcomp
{
    int i;
};

bool operator < (distcomp A, distcomp B)
{
    if(min_dist[A.i] == min_dist[B.i]) return A.i < B.i;
    return min_dist[A.i] < min_dist[B.i];
}








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

    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;
    set<distcomp> tbv;
    for(int i = 1; i <= R; i++)
        for(int j = 1; j <= C; j++)
            if(!blocked[pos(i, j)])
                tbv.insert(distcomp{pos(i, j)});


    while(!tbv.empty())
    {
        u = tbv.begin()->i;
        tbv.erase(tbv.begin());

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

            if(min_dist[v] > min_dist[u] + w)
            {
                tbv.erase(distcomp{v});
                min_dist[v] = min_dist[u] + w;
                tbv.insert(distcomp{v});
            }
        }
    }


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

Compilation message (stderr)

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

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