Submission #785654

#	Time	Username	Problem	Language	Result	Execution time	Memory
785654		KLPP	Maze (JOI23_ho_t3)	C++14	86 / 100	2063 ms	100548 KiB

Main

#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<1000000000> 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]==1)return;
	b[hsh]=1;
	if(N==1){
		if(valid(x,y) && dist[x][y]==1000000000){
			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 (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6