oj.uz

Submission #785644

# Submission time Handle Problem Language Result Execution time Memory
785644 2023-07-17T11:10:48 Z KLPP Maze (JOI23_ho_t3) C++14
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

int r,c,n;
int valid(int x, int y){
	if(x>=0 && x<r && y>=0 && y<c)return true;
	return false;
}
bitset<350000000> b;
#define MAX 24
deque<tuple<int,int,int> >q;
vector<vector<int> >dist;
int D;
void solve(int x, int y, int N, int cnt){
	int hsh=cnt+MAX*(y+n+(c+n)*(x+n));
	if(b[hsh]){
		return;
	}
	b[hsh]=1;
	if(N==1){
		if(valid(x,y)){
			dist[x][y]=D+1;
			q.push_back({x,y,D+1});
		}
		return;
	}
	if(N%2==0){
		N/=2;
		solve(x,y,N,cnt+1);
		solve(x+N,y,N,cnt+1);
		solve(x,y+N,N,cnt+1);
		solve(x+N,y+N,N,cnt+1);
		return;
	}
	N/=2;
	solve(x,y,N+1,cnt+1);
	solve(x+N,y,N+1,cnt+1);
	solve(x,y+N,N+1,cnt+1);
	solve(x+N,y+N,N+1,cnt+1);
}
void solve(){
	cin>>r>>c>>n;
	
	int sx,sy;
	cin>>sx>>sy;
	sx--;sy--;
	int gx,gy;
	cin>>gx>>gy;
	gx--;gy--;
	vector<string> V(r);
	rep(i,0,r)cin>>V[i];
	dist.resize(r);
	rep(i,0,r)dist[i].resize(c,1000000000);
	dist[sx][sy]=0;
	q.push_back({sx,sy,0});
	while(!q.empty()){
		auto [x,y,d]=q.front();
		q.pop_front();
		D=d;
		if(d>dist[x][y])continue;
		if(V[x][y]=='.'){
			rep(dx,x-1,x+2){
				rep(dy,y-1,y+2){
					if(abs(dx-x)+abs(dy-y)==1){
						if(valid(dx,dy)){
							if(dist[dx][dy]>d){
								dist[dx][dy]=d;
								q.push_front({dx,dy,d});
							}
						}
					}
				}
			}
		}
		solve(x-n,y-n+1,2*n-1,0);
		solve(x-n+1,y-n,2*n-1,0);
		solve(x-n+1,y-n+1,2*n-1,0);
		solve(x-n+2,y-n+1,2*n-1,0);
		solve(x-n+1,y-n+2,2*n-1,0);
	}
	cout<<dist[gx][gy]<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:65:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |   auto [x,y,d]=q.front();
      |        ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 240 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 240 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 240 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -