Submission #463683

#	Time	Username	Problem	Language	Result	Execution time	Memory
463683		AdamGS	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	117 ms	21624 KiB

adventure

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") 
#pragma GCC option("arch=native","tune=native","no-zero-upper") 
#pragma GCC target("avx2","popcnt","rdrnd","bmi2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=507, INF=1e9+7;
string T[LIM];
int odl[LIM*LIM];
vector<pair<int,int>>V[LIM*LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	rep(i, n) cin >> T[i];
	rep(i, n) rep(j, m) if(T[i][j]!='X')  {
		int ile=0;
		if(T[i][j]=='E') ile=3;
		if(T[i][j]=='S') ile=2;
		if(T[i][j]=='W') ile=1;
		if(i>0) V[i*m+j].pb({(i-1)*m+j, ile});
		ile=(ile+1)%4;
		if(j<m-1) V[i*m+j].pb({i*m+j+1, ile});
		ile=(ile+1)%4;
		if(i<n-1) V[i*m+j].pb({(i+1)*m+j, ile});
		ile=(ile+1)%4;
		if(j>0) V[i*m+j].pb({i*m+j-1, ile});
	}
	rep(i, n*m) odl[i]=INF;
	priority_queue<pair<int,int>>q;
	q.push({0, 0});
	while(!q.empty()) {
		int p=q.top().nd, o=-q.top().st; q.pop();
		if(odl[p]<o) continue;
		odl[p]=o;
		for(auto i : V[p]) if(odl[i.st]>odl[p]+i.nd) {
			q.push({-odl[p]-i.nd, i.st});
		}
	}
	cout << (odl[n*m-1]==INF?-1:odl[n*m-1]) << '\n';
}

Compilation message (stderr)

adventure.cpp:2: warning: ignoring '#pragma GCC option' [-Wunknown-pragmas]
    2 | #pragma GCC option("arch=native","tune=native","no-zero-upper")
      |

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