oj.uz

Submission #150891

# Submission time Handle Problem Language Result Execution time Memory
150891 2019-09-01T10:04:33 Z cheetose Portals (BOI14_portals) C++11
100 / 100
 686 ms 124916 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 y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#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 long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> 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 ll MOD = 1000000007;
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,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

char s[1000][1001];
int U[1000][1000],D[1000][1000],L[1000][1000],R[1000][1000];
VPi v[1000000];
int dist[1000000];
bool chk[1000000];
int n,m;
inline int Z(int x,int y){return x*m+y;}
int main() {
	fill(dist,dist+1000000,INF);
	scanf("%d%d",&n,&m);
	fup(i,0,n-1,1)scanf("%s",s[i]);
	int S,E;
	fup(i,0,n-1,1)
		fup(j,0,m-1,1)
	{
		if(s[i][j]=='S')S=Z(i,j);
		if(s[i][j]=='C')E=Z(i,j);
	}
	fup(i,0,n-1,1)
	{
		int p=-1;
		fup(j,0,m-1,1)
		{
			if(s[i][j]=='#')p=j;
			else L[i][j]=p;
		}
		p=m;
		fdn(j,m-1,0,1)
		{
			if(s[i][j]=='#')p=j;
			else R[i][j]=p;
		}
	}
	fup(j,0,m-1,1)
	{
		int p=-1;
		fup(i,0,n-1,1)
		{
			if(s[i][j]=='#')p=i;
			else U[i][j]=p;
		}
		p=n;
		fdn(i,n-1,0,1)
		{
			if(s[i][j]=='#')p=i;
			else D[i][j]=p;
		}
	}
	fup(x,0,n-1,1)
		fup(y,0,m-1,1)
	{
		if(s[x][y]=='#')continue;
		int now=Z(x,y);
		fup(i,0,3,1)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=0 && nx<n && ny>=0 && ny<m && s[nx][ny]!='#')
				v[now].pb(mp(Z(nx,ny),1));
		}
		int mm=min({abs(x-U[x][y]),abs(x-D[x][y]),abs(y-L[x][y]),abs(y-R[x][y])});
		int next=Z(U[x][y]+1,y);
		v[now].pb(mp(next,mm));
		next=Z(D[x][y]-1,y);
		v[now].pb(mp(next,mm));
		next=Z(x,L[x][y]+1);
		v[now].pb(mp(next,mm));
		next=Z(x,R[x][y]-1);
		v[now].pb(mp(next,mm));
	}
	priority_queue<Pi> q;
	dist[S] = 0;
	q.push({ 0,S });
	while (!q.empty())
	{
		int x = q.top().Y;
		q.pop();
		if (chk[x])continue;
		chk[x] = 1;
		for (const auto& p : v[x])
		{
			int next = p.X, cost = p.Y;
			if (dist[next] > dist[x]+cost)
			{
				dist[next] = dist[x] + cost;
				q.push({ -dist[next],next });
			}
		}
	}
	printf("%d",dist[E]);
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
portals.cpp:73: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]);
                ~~~~~^~~~~~~~~~~
portals.cpp:151:8: warning: 'E' may be used uninitialized in this function [-Wmaybe-uninitialized]
  printf("%d",dist[E]);
  ~~~~~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 27896 KB Output is correct
2 Correct 26 ms 27896 KB Output is correct
3 Correct 27 ms 27896 KB Output is correct
4 Correct 26 ms 27768 KB Output is correct
5 Correct 26 ms 27896 KB Output is correct
6 Correct 26 ms 27896 KB Output is correct
7 Correct 26 ms 28024 KB Output is correct
8 Correct 30 ms 28024 KB Output is correct
9 Correct 27 ms 27896 KB Output is correct
10 Correct 30 ms 27768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27896 KB Output is correct
2 Correct 27 ms 27896 KB Output is correct
3 Correct 27 ms 27900 KB Output is correct
4 Correct 29 ms 27776 KB Output is correct
5 Correct 31 ms 27980 KB Output is correct
6 Correct 27 ms 27896 KB Output is correct
7 Correct 27 ms 27896 KB Output is correct
8 Correct 26 ms 27896 KB Output is correct
9 Correct 28 ms 28792 KB Output is correct
10 Correct 28 ms 28792 KB Output is correct
11 Correct 28 ms 28664 KB Output is correct
12 Correct 28 ms 28664 KB Output is correct
13 Correct 28 ms 28664 KB Output is correct
14 Correct 27 ms 27896 KB Output is correct
15 Correct 28 ms 28664 KB Output is correct
16 Correct 26 ms 27768 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 27836 KB Output is correct
2 Correct 27 ms 27940 KB Output is correct
3 Correct 26 ms 27896 KB Output is correct
4 Correct 27 ms 27828 KB Output is correct
5 Correct 40 ms 33016 KB Output is correct
6 Correct 42 ms 32992 KB Output is correct
7 Correct 43 ms 33272 KB Output is correct
8 Correct 38 ms 33272 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 27776 KB Output is correct
2 Correct 26 ms 27896 KB Output is correct
3 Correct 30 ms 27924 KB Output is correct
4 Correct 30 ms 27800 KB Output is correct
5 Correct 27 ms 27900 KB Output is correct
6 Correct 26 ms 27896 KB Output is correct
7 Correct 26 ms 27896 KB Output is correct
8 Correct 26 ms 27912 KB Output is correct
9 Correct 28 ms 28792 KB Output is correct
10 Correct 28 ms 28756 KB Output is correct
11 Correct 28 ms 28664 KB Output is correct
12 Correct 28 ms 28664 KB Output is correct
13 Correct 28 ms 28664 KB Output is correct
14 Correct 40 ms 32888 KB Output is correct
15 Correct 41 ms 33020 KB Output is correct
16 Correct 45 ms 33272 KB Output is correct
17 Correct 42 ms 33144 KB Output is correct
18 Correct 44 ms 33528 KB Output is correct
19 Correct 48 ms 34296 KB Output is correct
20 Correct 48 ms 34276 KB Output is correct
21 Correct 40 ms 33016 KB Output is correct
22 Correct 40 ms 33016 KB Output is correct
23 Correct 42 ms 33116 KB Output is correct
24 Correct 46 ms 34296 KB Output is correct
25 Correct 27 ms 27868 KB Output is correct
26 Correct 28 ms 28792 KB Output is correct
27 Correct 26 ms 27768 KB Output is correct
28 Correct 38 ms 33272 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 27768 KB Output is correct
2 Correct 26 ms 27892 KB Output is correct
3 Correct 26 ms 27896 KB Output is correct
4 Correct 26 ms 27896 KB Output is correct
5 Correct 26 ms 27896 KB Output is correct
6 Correct 27 ms 27896 KB Output is correct
7 Correct 26 ms 27900 KB Output is correct
8 Correct 27 ms 27896 KB Output is correct
9 Correct 29 ms 28716 KB Output is correct
10 Correct 28 ms 28708 KB Output is correct
11 Correct 28 ms 28664 KB Output is correct
12 Correct 28 ms 28664 KB Output is correct
13 Correct 28 ms 28664 KB Output is correct
14 Correct 40 ms 32984 KB Output is correct
15 Correct 43 ms 33144 KB Output is correct
16 Correct 43 ms 33192 KB Output is correct
17 Correct 42 ms 33244 KB Output is correct
18 Correct 45 ms 33656 KB Output is correct
19 Correct 49 ms 34296 KB Output is correct
20 Correct 49 ms 34340 KB Output is correct
21 Correct 40 ms 33016 KB Output is correct
22 Correct 40 ms 33024 KB Output is correct
23 Correct 41 ms 33016 KB Output is correct
24 Correct 444 ms 100020 KB Output is correct
25 Correct 686 ms 124864 KB Output is correct
26 Correct 642 ms 124916 KB Output is correct
27 Correct 616 ms 124620 KB Output is correct
28 Correct 356 ms 91104 KB Output is correct
29 Correct 390 ms 92188 KB Output is correct
30 Correct 416 ms 93276 KB Output is correct
31 Correct 48 ms 34296 KB Output is correct
32 Correct 615 ms 124528 KB Output is correct
33 Correct 27 ms 27768 KB Output is correct
34 Correct 28 ms 28664 KB Output is correct
35 Correct 466 ms 105084 KB Output is correct
36 Correct 27 ms 27768 KB Output is correct
37 Correct 38 ms 33272 KB Output is correct
38 Correct 336 ms 98584 KB Output is correct
39 Correct 301 ms 85624 KB Output is correct