oj.uz

Submission #141671

# Submission time Handle Problem Language Result Execution time Memory
141671 2019-08-08T18:23:50 Z Ort Portal (COCI17_portal) C++11
120 / 120
 88 ms 5992 KB 
#include<bits/stdc++.h>
#define MEM(a, b) memset(a, (b), sizeof(a))
#define ALL(c) (c).begin(),(c).end()
#define LINF (int)1e18
#define INF (int)1e9
#define ll long long
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 510
 
using namespace std;
 
typedef pair<int,int> pii;
 
int n, m, si, sj, ei, ej, nx, ny, mm;
string mat[MAX];
int path[4][MAX][MAX], v[MAX][MAX];
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};
 
struct point{
	int y, x, d;
	point(int y, int x, int d) {
		this->y = y;
		this->x = x;
		this->d = d;
	}
	bool operator<(const point &pn) const{
		if(d==pn.d) {
			if(y==pn.y) return x<pn.x;
			return y<pn.y;
		}
		return d<pn.d;
	}
};

set<point> s;
 
inline bool check(int y, int x) {return (y>=0 && y<n && x>=0 && x<m && mat[y][x]!='#');}
 
inline void preprocess_paths() {
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) {
			if(mat[i][j]=='#') continue;
			if(mat[i][j-1]=='#')
				for(int k=j;k<m;k++) {
					if(mat[i][k]=='#') break;
					path[0][i][k] = k-j;
				}
			if(mat[i][j+1]=='#')
				for(int k=j;k>=0;k--) {
					if(mat[i][k]=='#') break;
					path[1][i][k] = j-k;
				}
			if(mat[i-1][j]=='#')
				for(int k=i;k<n;k++) {
					if(mat[k][j]=='#') break;
					path[2][k][j] = k-i;
				}	
			if(mat[i+1][j]=='#')
				for(int k=i;k>=0;k--) {
					if(mat[k][j]=='#') break;
					path[3][k][j] = i-k;
				}
		}
}

inline void solve() {
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) v[i][j] = INF;
	s.insert(point(si,sj,0));
	v[si][sj] = 0;
	while(!s.empty()) {
		point c = *s.begin();
		s.erase(s.begin());
		for(int k=0;k<4;k++) {
			ny = c.y + dy[k];
			nx = c.x + dx[k];
			if(check(ny,nx))
				if(v[ny][nx]>c.d+1) {
					s.erase(point(ny,nx,v[ny][nx]));
					s.insert(point(ny,nx,c.d+1));
					v[ny][nx] = c.d+1;
				}
		}
		mm = min(path[0][c.y][c.x], min(path[1][c.y][c.x], min(path[2][c.y][c.x], path[3][c.y][c.x]))); mm++;
		ny = c.y; nx = c.x;
		nx = c.x - path[0][c.y][c.x];
		if(check(ny,nx))
			if(v[ny][nx]>mm+c.d)
				s.erase(point(ny,nx,v[ny][nx])), s.insert(point(ny,nx,mm+c.d)), v[ny][nx] = mm+c.d;
		ny = c.y; nx = c.x;
		nx = c.x + path[1][c.y][c.x];
		if(check(ny,nx))
			if(v[ny][nx]>mm+c.d)
				s.erase(point(ny,nx,v[ny][nx])), s.insert(point(ny,nx,mm+c.d)), v[ny][nx] = mm+c.d;
		ny = c.y; nx = c.x;
		ny = c.y - path[2][c.y][c.x];
		if(check(ny,nx))
			if(v[ny][nx]>mm+c.d)
				s.erase(point(ny,nx,v[ny][nx])), s.insert(point(ny,nx,mm+c.d)), v[ny][nx] = mm+c.d;
		ny = c.y; nx = c.x;
		ny = c.y + path[3][c.y][c.x];
		if(check(ny,nx))
			if(v[ny][nx]>mm+c.d)
				s.erase(point(ny,nx,v[ny][nx])), s.insert(point(ny,nx,mm+c.d)), v[ny][nx] = mm+c.d;
	}
}

 
int main() {
	IO;
	cin >> n >> m;
	for(int i=0;i<n;i++) cin >> mat[i];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) {
			if(mat[i][j]=='C') si = i, sj = j;
			if(mat[i][j]=='F') ei = i, ej = j;
		}
	preprocess_paths();
	solve();
	if(v[ei][ej]==INF) cout << "nemoguce";
	else cout << v[ei][ej];
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 508 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 552 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2424 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 8 ms 1400 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2036 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 9 ms 1656 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4608 KB Output is correct
2 Correct 31 ms 3064 KB Output is correct
3 Correct 20 ms 3576 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 5280 KB Output is correct
2 Correct 13 ms 5752 KB Output is correct
3 Correct 34 ms 3704 KB Output is correct
4 Correct 30 ms 4644 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 5992 KB Output is correct
2 Correct 12 ms 5880 KB Output is correct
3 Correct 47 ms 5884 KB Output is correct
4 Correct 52 ms 5880 KB Output is correct