Submission #933375

#	Time	Username	Problem	Language	Result	Execution time	Memory
933375		pcc	Maze (JOI23_ho_t3)	C++17	100 / 100	1924 ms	522044 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

struct node{
	int lvl,r,c,d;
	node(){lvl = r = c = d = 0;}
	node(int lv,int rr,int cc,int dd):lvl(lv),r(rr),c(cc),d(dd){}
	bool operator<(node b)const{
		return d<b.d;
	}
	bool operator>(node b)const{
		return d>b.d;
	}
};

bitset<6000006> bound;
int R,C,N;
vector<string> arr;
vector<vector<int>> dist[5];
pii s,e;

deque<node> dq;

pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}};
pii dir2[] = {{1,1},{1,-1},{-1,-1},{-1,1}};

inline void add(int lvl,int r,int c,int d){
	if(lvl>4||r<0||c<0||r>=R||c>=C)return;
	//cout<<lvl<<','<<r<<' '<<c<<' '<<d<<endl;
	if(dist[lvl][r][c] != -1&&dist[lvl][r][c]<=d)return;
	dist[lvl][r][c] = d;
	if(dq.empty()||dq.back().d<=d)dq.push_back(node(lvl,r,c,d));
	else dq.push_front(node(lvl,r,c,d));
}

void add_center(int r,int c,int d){//extend radius of N*2-1 square
	pii row = {max((int)0,r-N+1),min(r+N-1,R-1)};
	pii col = {max((int)0,c-N+1),min(c+N-1,C-1)};
	for(int i = 0;i<4;i++){
		int nr = r-dir2[i].fs*(N-1),nc = c-dir2[i].sc*(N-1);
		if(nr>=0&&nr<R&&nc>=0&&nc<C)add(i,nr,nc,d);
		else {
			nr = max((int)0,nr),nr = min(nr,R-1),nc = max((int)0,nc),nc = min(nc,C-1);
			int er,ec;
			if(dir2[i].fs>0)er = (nr+N*2-2)/(N*2-1)*(N*2-1);
			else er = nr/(N*2-1)*(N*2-1);
			if(dir2[i].sc>0)ec = (nc+N*2-2)/(N*2-1)*(N*2-1);
			else ec = nc/(N*2-1)*(N*2-1);
			er = min(er,R-1),ec = min(ec,C-1);
			if(row.fs<=er&&er<=row.sc&&col.fs<=ec&&ec<=col.sc)add(i,nr,nc,d);
		}
	}
	return;
}

void BFS(pii s){
	add(4,s.fs,s.sc,0);
	dist[4][s.fs][s.sc] = 0;
	while(!dq.empty()){
		auto now = dq.front();
		dq.pop_front();
		//cout<<now.lvl<<','<<now.r<<' '<<now.c<<':'<<now.d<<":"<<dist[now.lvl][now.r][now.c]<<endl;
		assert(dist[now.lvl][now.r][now.c]<=now.d);
		if(dist[now.lvl][now.r][now.c] != now.d)continue;
		if(now.lvl == 4){
			add_center(now.r,now.c,now.d+1);
			for(auto &d:dir){
				int nr = d.fs+now.r,nc = d.sc+now.c;
				//cout<<nr<<','<<nc<<endl;
				if(nr>=0&&nc>=0&&nr<R&&nc<C){
					add_center(nr,nc,now.d+1);
					add(4,nr,nc,now.d+(arr[nr][nc] == '#'));
				}
			}
		}
		else{
			add(4,now.r,now.c,now.d);
			int nr = now.r+dir2[now.lvl].fs,nc = now.c+dir2[now.lvl].sc;
			if(nr>=0&&nr<R&&!bound[now.r])add(now.lvl,nr,now.c,now.d);
			if(nc>=0&&nc<C&&!bound[now.c])add(now.lvl,now.r,nc,now.d);
		}
	}
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>R>>C>>N;
	arr = vector<string>(R);
	dist[0] = dist[1] = dist[2] = dist[3] = dist[4] = vector<vector<int>>(R,vector<int>(C,-1));
	for(int i = 0;i<6e6;i++)bound[i] = (i%(N*2-1)==0);
	cin>>s.fs>>s.sc>>e.fs>>e.sc;
	s.fs--,s.sc--,e.fs--,e.sc--;
	for(auto &i:arr)cin>>i;
	BFS(s);
	cout<<dist[4][e.fs][e.sc];
}

Compilation message (stderr)

Main.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main(){
      | ^~~~

• 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: 8 / 8
• Subtask 8: 6 / 6