Submission #240339

#	Time	Username	Problem	Language	Result	Execution time	Memory
240339		blacktulip	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	239 ms	44872 KiB

adventure

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
typedef pair< lo,PII > PIII;
 
#define fi first
#define se second
#define mp make_pair
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;
 
int n,m,b[li],a[li],k,flag,t,vis[505][505],d[505][505];
int cev;
string s[li];
vector<int> v;

inline void sp(){
	priority_queue<PIII> pq;
	pq.push(mp(0,mp(1,0)));
	while(pq.size()){
		//~ cout<<"(*(\n"<<endl;
		int para=-pq.top().fi;
		int satir=pq.top().se.fi;
		int sutun=pq.top().se.se;
		pq.pop();
		if(satir<=0 || sutun<0 || satir>n || sutun>=m)continue ;
		if(vis[satir][sutun]==1)continue ;
		d[satir][sutun]=para;
		//~ if(s[satir][sutun]=='X')continue ;
		vis[satir][sutun]=1;
		if(s[satir][sutun]=='N'){
			pq.push(mp(-para,mp(satir-1,sutun)));
			pq.push(mp(-(para+1),mp(satir,sutun+1)));
			pq.push(mp(-(para+2),mp(satir+1,sutun)));
			pq.push(mp(-(para+3),mp(satir,sutun-1)));
		}
		if(s[satir][sutun]=='E'){
			pq.push(mp(-para,mp(satir,sutun+1)));
			pq.push(mp(-(para+1),mp(satir+1,sutun)));
			pq.push(mp(-(para+3),mp(satir-1,sutun)));
			pq.push(mp(-(para+2),mp(satir,sutun-1)));
		}
		if(s[satir][sutun]=='S'){
			pq.push(mp(-para,mp(satir+1,sutun)));
			pq.push(mp(-(para+3),mp(satir,sutun+1)));
			pq.push(mp(-(para+2),mp(satir-1,sutun)));
			pq.push(mp(-(para+1),mp(satir,sutun-1)));
		}
		if(s[satir][sutun]=='W'){
			pq.push(mp(-para,mp(satir,sutun-1)));
			pq.push(mp(-(para+2),mp(satir,sutun+1)));
			pq.push(mp(-(para+3),mp(satir+1,sutun)));
			pq.push(mp(-(para+1),mp(satir-1,sutun)));
		}
	}
}

main(void){
	memset(d,-1,sizeof(d));
	scanf("%lld %lld",&n,&m);
	FOR{
		cin>>s[i];
	}
	sp();
	printf("%lld\n",d[n][m-1]);
	return 0;
}

Compilation message (stderr)

adventure.cpp:73:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
adventure.cpp: In function 'int main()':
adventure.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50