Submission #31383

#	Time	Username	Problem	Language	Result	Execution time	Memory
31383		imaxblue	Portals (BOI14_portals)	C++14	70 / 100	1000 ms	37572 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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 pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#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 foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, m, sx, sy, dx, dy, X, Y, P, D;
int wd[1005][1005], cx[4]={0, 1, 0, -1}, cy[4]={-1, 0, 1, 0};
char ch;
bool u[1005][1005][6], w[1005][1005];
queue<p3i> q;
pq<pair<pii, pii> > q2;
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){
            if (!w[l][l2]) q.push(mp(mp(l, l2), -1));
        }
    }
    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(mp(0, 4), mp(sx, sy)));
    while(!q2.empty()){
        X=q2.top().y.x; Y=q2.top().y.y; D=-q2.top().x.x; P=q2.top().x.y; q2.pop();

        if (!w[X][Y] || u[X][Y][P]) continue;
        u[X][Y][P]=1;
        //cout << X << ' '<< Y << ' ' << D << endl;
        if (P==4 || !w[X+cx[P]][Y+cy[P]]){
            if (X==dx && Y==dy){
                cout << D << endl;
                return 0;
            }
            fox(l, 4){
                q2.push(mp(mp(-D-1, 4), mp(X+cx[l], Y+cy[l])));
                q2.push(mp(mp(-D-wd[X][Y]-1, l), mp(X+cx[l], Y+cy[l])));
            }
            continue;
        }
        q2.push(mp(mp(-D, P), mp(X+cx[P], Y+cy[P])));
    }
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:35: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:38: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: 0 / 30