Submission #270291

#	Time	Username	Problem	Language	Result	Execution time	Memory
270291		Killer2501	Portals (BOI14_portals)	C++14	100 / 100	869 ms	119864 KiB

portals

#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define fi first
#define se second
#define pll pair<ll, ll>
using namespace std;
const ll N = 1e6 + 5;
const ll mod = 1e9 + 7;
ll n, sum= 0, m, tong, k, ans, T, t;

ll b[N], d[N];
string s;
vector<pll> adj[N];
ll f(ll i, ll j)
{
    return (i-1) * m + j;
}
char c[N];
queue<pll> ds;
void bfs()
{
    while(!ds.empty())
    {
        pll u = ds.front();
        ds.pop();
        int j = (u.se % m == 0) ? m : (u.se % m), i = (u.se - j) / m + 1;
        //cout << i <<" "<<j<<'\n';
        if(i > 1)
        {
            k = f(i-1, j);
            if(b[k] > u.fi + 1)
            {
                b[k] = u.fi + 1;
                ds.push({b[k], k});
            }
        }
        if(j > 1)
        {
            k = f(i, j-1);
            if(b[k] > u.fi + 1)
            {
                b[k] = u.fi + 1;
                ds.push({b[k], k});
            }
        }
        if(i < n)
        {
            k = f(i+1, j);
            if(b[k] > u.fi + 1)
            {
                b[k] = u.fi + 1;
                ds.push({b[k], k});
            }
        }
        if(j < m)
        {
            k = f(i, j+1);
            if(b[k] > u.fi + 1)
            {
                b[k] = u.fi + 1;
                ds.push({b[k], k});
            }
        }
    }
}
inline void sol()
{
    cin >> n >> m;
    ll sa, fn;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            k = f(i, j);
            cin >> c[k];
            if(c[k] == 'S')
            {
                sa = k;
            }
            if(c[k] == 'C')
            {
                fn = k;
            }
            b[k] = mod;
            d[k] = mod;
            if(c[k] == '#')
            {
                ds.push({0, k});
                b[k] = 0;
            }

        }
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= m; j ++)
            {
            k = f(i, j);
            if(i > 1 && c[f(i-1, j)] != '#')adj[k].pb({1, f(i-1, j)});
            if(j > 1 && c[f(i, j-1)] != '#')adj[k].pb({1, f(i, j-1)});
            if(i < n && c[f(i+1, j)] != '#')adj[k].pb({1, f(i+1, j)});
            if(j < m && c[f(i, j+1)] != '#')adj[k].pb({1, f(i, j+1)});
            }
        }
        for(int i = 1; i <= n; i ++)
        {
            k = f(i, 1);
            if(c[k] != '#')
            {
                b[k] = 1;
                ds.push({b[k], k});
            }
            k = f(i, m);
            if(c[k] != '#')
            {
                b[k] = 1;
                ds.push({b[k], k});
            }
        }
        for(int i = 1; i <= m; i ++)
        {
            k = f(1, i);
            if(c[k] != '#')
            {
                b[k] = 1;
                ds.push({b[k], k});
            }
            k = f(n, i);
            if(c[k] != '#')
            {
                b[k] = 1;
                ds.push({b[k], k});
            }
        }
    bfs();
    for(int i = 1; i <= n; i ++)
    {
        stack<ll> l, r;
        l.push(0);
        r.push(m+1);
        for(int j = 1; j <= m; j ++)
        {
            k = f(i, j);
            //cout << b[k] <<" ";

            t = l.top() + 1;
            adj[k].pb({b[k], f(i, t)});
            if(c[k] == '#')l.push(j);
        }
        //cout << '\n';
        for(int j = m; j > 0; j --)
        {
            k = f(i, j);
            t = r.top() - 1;
            adj[k].pb({b[k], f(i, t)});
            if(c[k] == '#')r.push(j);
        }
    }
    for(int i = 1; i <= m; i ++)
    {
        stack<ll> l, r;
        l.push(0);
        r.push(n+1);
        for(int j = 1; j <= n; j ++)
        {
            k = f(j, i);
            t = l.top() + 1;
            //cout << j <<" "<< i <<" "<<t<<'\n';
            adj[k].pb({b[k], f(t, i)});
            if(c[k] == '#')l.push(j);
        }
        for(int j = n; j > 0; j --)
        {
            k = f(j, i);
            t = r.top() - 1;
            adj[k].pb({b[k], f(t, i)});
            if(c[k] == '#')r.push(j);
        }
    }
    priority_queue< pll, vector<pll>, greater<pll> >pr;
    pr.push({0, sa});
    d[sa] = 0;
    while(!pr.empty())
    {
        pll u = pr.top();
        pr.pop();
        if(d[u.se] != u.fi)continue;
        int j = (u.se % m == 0) ? m : u.se  % m, i = (u.se - j) / m + 1;
        //cout << i <<" "<<j<<" "<<u.fi<<'\n';
        for(pll v : adj[u.se])
        {
            if(d[v.se] > d[u.se] + v.fi)
            {

                d[v.se] = d[u.se] + v.fi;
                pr.push({d[v.se], v.se});
            }
        }
    }

    cout << d[fn];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sol();
}

Compilation message (stderr)

portals.cpp: In function 'void sol()':
portals.cpp:71:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   71 |     for(int i = 1; i <= n; i ++)
      |     ^~~
portals.cpp:93:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   93 |         for(int i = 1; i <= n; i ++)
      |         ^~~
portals.cpp:187:50: warning: unused variable 'i' [-Wunused-variable]
  187 |         int j = (u.se % m == 0) ? m : u.se  % m, i = (u.se - j) / m + 1;
      |                                                  ^
portals.cpp:181:11: warning: 'sa' may be used uninitialized in this function [-Wmaybe-uninitialized]
  181 |     d[sa] = 0;
      |     ~~~~~~^~~
portals.cpp:200:17: warning: 'fn' may be used uninitialized in this function [-Wmaybe-uninitialized]
  200 |     cout << d[fn];
      |                 ^

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