oj.uz

Submission #1046686

# Submission time Handle Problem Language Result Execution time Memory
1046686 2024-08-06T20:25:28 Z 1L1YA Maze (JOI23_ho_t3) C++17
0 / 100
 46 ms 329444 KB 
//1L1YA
 
#include<bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;
 
#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=6e6+11;
const int lg=23;
 
int n,m,k,xs,ys,xt,yt,x[4]={1,-1,0,0},y[4]={0,0,1,-1};
vector<int> d[N];
string s[N];
 
void bfs(){
	queue<pii> Q;
	deque<pair<pii,pii>> QQ;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			d[i][j]=inf;
	d[xs][ys]=0;
	QQ.Pb({{xs,ys},{0,0}});
	while(!QQ.empty()){
		int p=QQ.front().F.F,q=QQ.front().F.S;QQ.pop_front();
		Q.push({p,q});
		for(int i=0;i<4;i++)
			if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && d[p+x[i]][q+y[i]] && s[p+x[i]][q+y[i]]=='.'){
				d[p+x[i]][q+y[i]]=0;
				QQ.Pb({{p+x[i],q+y[i]},{0,0}});
			}
	}
	while(!Q.empty()){
		while(!Q.empty()){
			int p=Q.front().F,q=Q.front().S;Q.pop();
			for(int i=0;i<4;i++)
				if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && d[p][q]+1<d[p+x[i]][q+y[i]]){
					d[p+x[i]][q+y[i]]=d[p][q]+1;
					QQ.Pb({{p+x[i],q+y[i]},{abs(x[i]),abs(y[i])}});
				}
		}
		while(!QQ.empty()){
			int p=QQ.front().F.F,q=QQ.front().F.S;
			pii val=QQ.front().S;
			QQ.pop_front();
			Q.push({p,q});
			if(q==9)	cout << '!' << sep << p << sep << q << sep << val.F << sep << val.S << endl;
			for(int i=0;i<4;i++)
				if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && d[p][q]<d[p+x[i]][q+y[i]] && ((val.F+abs(x[i])<=k && val.S+abs(y[i])<=k && (val.F+abs(x[i])<k || val.S+abs(y[i])<k)))){
					d[p+x[i]][q+y[i]]=d[p][q];
					QQ.push_front({{p+x[i],q+y[i]},{val.F+abs(x[i]),val.S+abs(y[i])}});
				}
				else if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && d[p][q]<d[p+x[i]][q+y[i]] && s[p+x[i]][q+y[i]]=='.'){
					d[p+x[i]][q+y[i]]=d[p][q];
					QQ.Pb({{p+x[i],q+y[i]},{val.F+abs(x[i]),val.S+abs(y[i])}});
				}
		}
	}
}
 
int main(){
	FastIO
 
	cin >> n >> m >> k >> xs >> ys >> xt >> yt;
	for(int i=1;i<=n;i++){
		cin >> s[i];
		s[i]='#'+s[i];
		d[i].resize(m+1);
	}
	bfs();
	//for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cout << d[i][j] << sep;cout << endl;}
	cout << d[xt][yt] << endl;
 
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 329044 KB Output is correct
2 Correct 44 ms 329044 KB Output is correct
3 Incorrect 46 ms 329040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 329196 KB Output is correct
2 Correct 44 ms 329040 KB Output is correct
3 Correct 44 ms 329040 KB Output is correct
4 Correct 46 ms 329208 KB Output is correct
5 Incorrect 44 ms 329072 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 329188 KB Output is correct
2 Correct 44 ms 329052 KB Output is correct
3 Correct 43 ms 329444 KB Output is correct
4 Correct 44 ms 329184 KB Output is correct
5 Correct 45 ms 329048 KB Output is correct
6 Incorrect 46 ms 329180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 329196 KB Output is correct
2 Correct 44 ms 329040 KB Output is correct
3 Correct 44 ms 329040 KB Output is correct
4 Correct 46 ms 329208 KB Output is correct
5 Incorrect 44 ms 329072 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 329196 KB Output is correct
2 Correct 44 ms 329040 KB Output is correct
3 Correct 44 ms 329040 KB Output is correct
4 Correct 46 ms 329208 KB Output is correct
5 Incorrect 44 ms 329072 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 329044 KB Output is correct
2 Correct 44 ms 329044 KB Output is correct
3 Incorrect 46 ms 329040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 329044 KB Output is correct
2 Correct 44 ms 329044 KB Output is correct
3 Incorrect 46 ms 329040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 329044 KB Output is correct
2 Correct 44 ms 329044 KB Output is correct
3 Incorrect 46 ms 329040 KB Output isn't correct
4 Halted 0 ms 0 KB -