Submission #31388

#	Time	Username	Problem	Language	Result	Execution time	Memory
31388		imaxblue	Portals (BOI14_portals)	C++14	100 / 100	769 ms	57888 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)

int n, m, sx, sy, dx, dy, X, Y, P, D, A, B;
int wd[1005][1005], cx[4]={0, 1, 0, -1}, cy[4]={-1, 0, 1, 0}, nxtw[1005][1005][4];
char ch;
bool u[2050005], w[1005][1005];
queue<p3i> q;
pq<pii> q2;
int dfs(int X, int Y, int D){
    if (!w[X][Y]) return 0;
    if (nxtw[X][Y][D]!=0) return nxtw[X][Y][D];
    nxtw[X][Y][D]=dfs(X+cx[D], Y+cy[D], D)+1;
    return nxtw[X][Y][D];
}
int main(){
    flood(wd);
    scanf("%i%i", &n, &m);
    fox1(l, n){
        fox1(l2, m){
            scanf(" %c", &ch);
            if (ch!='#') w[l][l2]=1;
            if (ch=='S'){sx=l; sy=l2;}
            if (ch=='C'){dx=l; dy=l2;}
        }
    }
    fox(l, n+2){
        fox(l2, m+2){
            //cout << l << ' ' << l2 << endl;
            fox(l3, 4){
                dfs(l, l2, l3);
                //cout << nxtw[l][l2][l3] << ":";
            }
            //cout << ' ';
            if (!w[l][l2]) q.push(mp(mp(l, l2), -1));
        }
        //cout << endl;
    }
    while(!q.empty()){
        X=q.front().x.x; Y=q.front().x.y; D=q.front().y; q.pop();
        if (X<0 || Y<0 || X>n+1 || Y>m+1) continue;
        if (wd[X][Y]<=D) continue;
        wd[X][Y]=D;
        q.push(mp(mp(X+1, Y), D+1));
        q.push(mp(mp(X-1, Y), D+1));
        q.push(mp(mp(X, Y+1), D+1));
        q.push(mp(mp(X, Y-1), D+1));
    }
    //fox1(l, n){
        //fox1(l2, m) cout << wd[l][l2] << ' '; cout << endl;
    //}
    q2.push(mp(0, (sx << 11)+sy));
    while(!q2.empty()){
        X=q2.top().y;
        D=-q2.top().x; q2.pop();

        //cout << X << ' '<< A << ' ' << B << ' ' << D << endl;
        if (!w[A=(X >> 11)][B=(X & ((1 << 11)-1))] || u[X]) continue;

        u[X]=1;
        if (A==dx && B==dy){
            cout << D << endl;
            return 0;
        }
        fox(l, 4){
            if (w[A+cx[l]][B+cy[l]] && !u[X+(cx[l] << 11)+cy[l]])
                q2.push(mp(-D-1, X+(cx[l] << 11)+cy[l]));
            if (w[A+cx[l]*(nxtw[A][B][l]-1)][B+cy[l]*(nxtw[A][B][l]-1)] &&
                !u[X+((cx[l]*(nxtw[A][B][l]-1) << 11)
                                         +cy[l]*(nxtw[A][B][l]-1))])
            q2.push(mp(-D-wd[A][B]-1, X+((cx[l]*(nxtw[A][B][l]-1) << 11)
                                         +cy[l]*(nxtw[A][B][l]-1))));
        }

    }
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:29:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i", &n, &m);
                          ^
portals.cpp:32:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &ch);
                              ^

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