Submission #74417

# Submission time Handle Problem Language Result Execution time Memory
74417 2018-09-01T06:01:53 Z cheetose Aquatic Labyrinth (FXCUP3_aqua) C++11
36 / 100
1713 ms 234800 KB
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define INF 1987654321987654321
#define PI 3.14159265358979323846264
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset(a,0,sizeof(a));
#define MEM_1(a) memset(a,-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 1000000009;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int ddx[] = { 0,0,1,1,1,-1,-1,-1 }, ddy[] = { 1,-1,1,0,-1,1,0,-1 };
 
char s[900][901];
VPll v[3240002];
ll dist[3240002];
bool chk[3240002];
int n;
inline int Z(int x,int y,int dir){return dir*n*n+x*n+y;}
const int SS=3240000,EE=3240001;
int main() {
	fill(dist,dist+3240002,INF);
	scanf("%d",&n);
	fup(i,0,n-1,1)scanf("%s",s[i]);
	Pi S,E;
	fup(i,0,n-1,1)
		fup(j,0,n-1,1)
	{
		if(s[i][j]=='M')S=mp(i,j);
		if(s[i][j]=='H')E=mp(i,j);
		if(s[i][j]=='.' || s[i][j]=='H')
		{
			if(i!=0&&s[i-1][j]!='W')v[Z(i,j,3)].pb(mp(Z(i-1,j,3),0));
			if(i!=n-1&&s[i+1][j]!='W')v[Z(i,j,2)].pb(mp(Z(i+1,j,2),0));
			if(j!=0&&s[i][j-1]!='W')v[Z(i,j,1)].pb(mp(Z(i,j-1,1),0));
			if(j!=n-1&&s[i][j+1]!='W')v[Z(i,j,0)].pb(mp(Z(i,j+1,0),0));
		}
	}
	fup(i,0,n-1,1)
	{
		int t=0, to=-1;
		fdn(j,n-1,0,1)
		{
			if(s[i][j]=='W')t++;
			else
			{
				if(to!=-1)
					fup(kk,0,3,1)v[Z(i,j,kk)].pb(mp(to,t*t));
				if(j!=0&&s[i][j-1]=='W')
				{
					to=Z(i,j,0);
					t=0;
				}
			}
		}
		t=0, to=-1;
		fup(j,0,n-1,1)
		{
			if(s[i][j]=='W')t++;
			else
			{
				if(to!=-1)fup(kk,0,3,1)v[Z(i,j,kk)].pb(mp(to,t*t));
				if(j!=n-1 && s[i][j+1]=='W')
				{
					to=Z(i,j,1);
					t=0;
				}
			}
		}
	}
	fup(j,0,n-1,1)
	{
		int t=0, to=-1;
		fdn(i,n-1,0,1)
		{
			if(s[i][j]=='W')t++;
			else
			{
				if(to!=-1)fup(kk,0,3,1)v[Z(i,j,kk)].pb(mp(to,t*t));
				if(i!=0&&s[i-1][j]=='W')
				{
					to=Z(i,j,2);
					t=0;
				}
			}
		}
		t=0, to=-1;
		fup(i,0,n-1,1)
		{
			if(s[i][j]=='W')t++;
			else
			{
				if(to!=-1)fup(kk,0,3,1)v[Z(i,j,kk)].pb(mp(to,t*t));
				if(i!=n-1&&s[i+1][j]=='W')
				{
					to=Z(i,j,3);
					t=0;
				}
			}
		}
	}
	priority_queue<Pll> q;
	fup(i,0,3,1)
	{
		v[SS].pb(mp(Z(S.X,S.Y,i),0));
		v[Z(E.X,E.Y,i)].pb(mp(EE,0));
	}
	dist[SS] = 0;
	q.push({ 0,SS });
	while (!q.empty())
	{
		ll x = q.top().Y;
		q.pop();
		if (chk[x])continue;
		chk[x] = 1;
		for (const auto& p : v[x])
		{
			ll next = p.X, cost = p.Y;
			if (dist[next] > dist[x]+cost)
			{
				dist[next] = dist[x] + cost;
				q.push({ -dist[next],next });
			}
		}
	}
	printf("%lld\n",dist[EE]==INF?-1:dist[EE]);
}

Compilation message

aqua.cpp: In function 'int main()':
aqua.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
aqua.cpp:70:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fup(i,0,n-1,1)scanf("%s",s[i]);
                ~~~~~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 85 ms 101752 KB Output is correct
2 Correct 86 ms 101908 KB Output is correct
3 Correct 84 ms 102028 KB Output is correct
4 Correct 85 ms 102608 KB Output is correct
5 Correct 87 ms 102904 KB Output is correct
6 Correct 95 ms 103800 KB Output is correct
7 Correct 98 ms 104184 KB Output is correct
8 Correct 100 ms 104312 KB Output is correct
9 Correct 90 ms 104312 KB Output is correct
10 Correct 83 ms 104312 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 85 ms 101752 KB Output is correct
2 Correct 86 ms 101908 KB Output is correct
3 Correct 84 ms 102028 KB Output is correct
4 Correct 85 ms 102608 KB Output is correct
5 Correct 87 ms 102904 KB Output is correct
6 Correct 95 ms 103800 KB Output is correct
7 Correct 98 ms 104184 KB Output is correct
8 Correct 100 ms 104312 KB Output is correct
9 Correct 90 ms 104312 KB Output is correct
10 Correct 83 ms 104312 KB Output is correct
11 Correct 361 ms 128004 KB Output is correct
12 Correct 571 ms 159576 KB Output is correct
13 Incorrect 1713 ms 234800 KB Output isn't correct
14 Halted 0 ms 0 KB -