Submission #115982

#	Time	Username	Problem	Language	Result	Execution time	Memory
115982		ckodser	Portals (BOI14_portals)	C++14	100 / 100	774 ms	166092 KiB

portals

#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1010;
const ll inf=1e9+900;
const ll maxm=maxn*maxn;
const ll di[4]={+1,-1,0,0};
const ll dj[4]={0,0,+1,-1};


vector<pii> ger[maxm];
ll dp[maxm];
vector<ll> vec[maxm];

ll fas(ll a,ll b){
    vec[0].pb(a);
    fill(dp,dp+maxm,inf);
    for(ll w=0;w<maxm;w++){
	for(auto v:vec[w]){
	    if(dp[v]==inf){
		dp[v]=w;
		if(v==b)return w;
		for(auto t:ger[v]){
		    if(dp[t.F]==inf){
			if(w+t.S<maxm){
			    vec[w+t.S].pb(t.F);	 
			}
		    }
		}	
	    }
	}
    }
    if(dp[b]==inf)dp[b]=-1;
    return dp[b];
}

string s[maxn];
ll minn[maxm];
ll ta[maxm][4];
ll n,m;

ll getid(ll a,ll b){
    return a*maxn+b;
}
bool val(ll a,ll b){
    return (!(a<0 || b<0 || a>=n || b>=m || s[a][b]=='#'));
}
void addYal(ll a,ll b,ll c){
    if(a==b)return;
    ger[a].pb(mp(b,c));
}	


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    	
    cin>>n>>m;
    for(ll i=0;i<n;i++){
	cin>>s[i];
    }
    fill(minn,minn+maxm,inf);
    queue<ll> qu;
    for(ll i=0;i<n;i++){
	for(ll j=0;j<m;j++){
	    ll id=getid(i,j);
	    if(s[i][j]!='#'){
		for(ll y=0;y<4;y++){
		    if(val(i+di[y],j+dj[y])){
			addYal(getid(i,j),getid(i+di[y],j+dj[y]),1);
		    }else if(minn[id]==inf){
			minn[id]=1;
			qu.push(id);
		    }
		}
	    }
	}
    }	
    while(qu.size()){
	ll v=qu.front();
	qu.pop();
	for(auto e:ger[v]){
	    ll u=e.F;
	    if(minn[u]==inf){
		minn[u]=minn[v]+1;
		qu.push(u);
	    }	
	}
    }
    for(ll i=0;i<n;i++){
	for(ll j=0;j<m;j++){
	    ll id=getid(i,j);
	    if(val(i+di[1],j+dj[1])){
		ta[id][1]=ta[getid(i+di[1],j+dj[1])][1];
	    }else{
		ta[id][1]=id;
	    }

	    if(val(i+di[3],j+dj[3])){
		ta[id][3]=ta[getid(i+di[3],j+dj[3])][3];
	    }else{
		ta[id][3]=id;
	    }
	}
    }
    for(ll i=n-1;i>=0;i--){
	for(ll j=m-1;j>=0;j--){
	    ll id=getid(i,j);
	    if(val(i+di[2],j+dj[2])){
		ta[id][2]=ta[getid(i+di[2],j+dj[2])][2];
	    }else{
		ta[id][2]=id;
	    }

	    if(val(i+di[0],j+dj[0])){
		ta[id][0]=ta[getid(i+di[0],j+dj[0])][0];
	    }else{
		ta[id][0]=id;
	    }
	}
    }
    ll start;
    ll end;
    for(ll i=0;i<n;i++){
	for(ll j=0;j<m;j++){
	    if(s[i][j]!='#'){
		ll id=getid(i,j);
		if(s[i][j]=='S')start=id;
		if(s[i][j]=='C')end=id;
		for(ll y=0;y<4;y++){
		    addYal(id,ta[id][y],minn[id]);
		}
	    }
	}
    }	
    cout<<fas(start,end);
}	

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:145:24: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<fas(start,end);
                        ^
portals.cpp:145:24: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]

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