Submission #733386

#	Time	Username	Problem	Language	Result	Execution time	Memory
733386		n0sk1ll	Portals (BOI14_portals)	C++17	100 / 100	210 ms	155432 KiB

portals

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

int n,m;
bool vis[1003][1003];
char tab[1003][1003];
bool portal[1003][1003];
vector<pii> placed;

bool moze(int i, int j)
{
    if (i<0 || i>=n) return false;
    if (j<0 || j>=m) return false;
    if (tab[i][j]=='#') return false;
    return true;
}

pii levo[1003][1003];
pii desno[1003][1003];
pii gore[1003][1003];
pii dole[1003][1003];

vector<pii> bfs[2'000'003];

int dist(int x, int y, pii sta)
{
    return abs(x-sta.xx) + abs(y-sta.yy);
}

int main()
{
    FAST;

    cin>>n>>m;
    ff(i,0,n) cin>>tab[i];

    ff(i,0,n) ff(j,0,m)
    {
        levo[i][j]={i,j};
        desno[i][j]={i,j};
        gore[i][j]={i,j};
        dole[i][j]={i,j};
    }

    ff(i,0,n) ff(j,0,m)
    {
        if (moze(i-1,j)) gore[i][j]=gore[i-1][j];
        if (moze(i,j-1)) levo[i][j]=levo[i][j-1];
    }
    bff(i,0,n) bff(j,0,m)
    {
        if (moze(i+1,j)) dole[i][j]=dole[i+1][j];
        if (moze(i,j+1)) desno[i][j]=desno[i][j+1];
    }

    ff(i,0,n) ff(j,0,m)
    {
        if (tab[i][j]=='S') bfs[0].pb({i,j});
    }

    fff(d,0,1'000'000) while (!bfs[d].empty())
    {
        auto [x,y]=bfs[d].back();
        bfs[d].popb();

        if (vis[x][y]) continue;
        vis[x][y]=true;
        if (tab[x][y]=='C') return cout<<d,0;

        pii U=gore[x][y];
        pii D=dole[x][y];
        pii L=levo[x][y];
        pii R=desno[x][y];

        int md=1'000'001;
        md=min(md,dist(x,y,U));
        md=min(md,dist(x,y,L));
        md=min(md,dist(x,y,R));
        md=min(md,dist(x,y,D));

        bfs[d+md+1].pb(U);
        bfs[d+md+1].pb(D);
        bfs[d+md+1].pb(L);
        bfs[d+md+1].pb(R);

        if (moze(x+1,y)) bfs[d+1].pb({x+1,y});
        if (moze(x-1,y)) bfs[d+1].pb({x-1,y});
        if (moze(x,y+1)) bfs[d+1].pb({x,y+1});
        if (moze(x,y-1)) bfs[d+1].pb({x,y-1});
    }
}

//Note to self: Check for overflow

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