Submission #675124

#	Time	Username	Problem	Language	Result	Execution time	Memory
675124		tamthegod	Portals (BOI14_portals)	C++14	31 / 100	2 ms	596 KiB

portals

// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e2 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int r, c;
string a[maxN];
pair<int, int> s, t;
int d[maxN][maxN];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<int> row[maxN], col[maxN];
struct TPQRect
{
    int x, y, dlab;
    bool operator < (const TPQRect& other) const
    {
        return other.dlab < dlab;
    }
    bool Valid() const
    {
        return d[x][y] == dlab;
    }
};
void ReadInput()
{
    cin >> r >> c;
    for(int i=1; i<=r; i++)
    {
        row[i].pb(0);
        row[i].pb(c + 1);
    }
    for(int i=1; i<=c; i++)
    {
        col[i].pb(0);
        col[i].pb(r + 1);
    }
    for(int i=1; i<=r; i++)
    {
        cin >> a[i];
        a[i] = ' ' + a[i];
        for(int j=1; j<=c; j++)
        {
            if(a[i][j] == 'S')
                s = {i, j};
            if(a[i][j] == 'C')
                t = {i, j};
            if(a[i][j] == '#')
            {
                row[i].pb(j);
                col[j].pb(i);
            }
        }
    }
    for(int i=1; i<=r; i++)
        sort(row[i].begin(), row[i].end());
    for(int i=1; i<=c; i++)
        sort(col[i].begin(), col[i].end());
}
void Dijkstra()
{
    priority_queue<TPQRect> pq;
    memset(d, 3, sizeof d);
    d[s.fi][s.se] = 0;
    pq.push({s.fi, s.se, 0});
    while(!pq.empty())
    {
        TPQRect R = pq.top();
        pq.pop();
        if(!R.Valid())
            continue;
        int x = R.x, y = R.y;
        for(int i=0; i<4; i++)
        {
            int u = x + dx[i], v = y + dy[i];
            if(u < 1 || u > r || v < 1 || v > c || a[u][v] == '#')
                continue;
            if(d[u][v] > d[x][y] + 1)
            {
                d[u][v] = d[x][y] + 1;
                pq.push({u, v, d[u][v]});
            }
        }
        vector<pair<int, int>> vc;
        int id = lower_bound(row[x].begin(), row[x].end(), y) - row[x].begin();
        vc.pb({x, row[x][id] - 1});
        id--;
        vc.pb({x, row[x][id] + 1});
        id = lower_bound(col[y].begin(), col[y].end(), x) - col[y].begin();
        vc.pb({col[y][id] - 1, y});
        id--;
        vc.pb({col[y][id] + 1, y});
        for(int i=0; i<4; i++)
            for(int j=0; j<4; j++)
            {
                int w = abs(x - vc[j].fi) + abs(y - vc[j].se) + 1;
                if(d[vc[i].fi][vc[i].se] > d[x][y] + w)
                {
                    d[vc[i].fi][vc[i].se] = d[x][y] + w;
                    pq.push({vc[i].fi, vc[i].se, d[vc[i].fi][vc[i].se]});
                }
            }
    }
}
void Solve()
{
    Dijkstra();
    cout << d[t.fi][t.se];
}
int32_t main()
{
    //freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

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