Submission #860530

#	Time	Username	Problem	Language	Result	Execution time	Memory
860530		NotLinux	Maze (JOI23_ho_t3)	C++17	0 / 100	1 ms	460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
void solve(){
	int r,c,n;
	cin >> r >> c >> n;	
	pair < int , int > s,g;
	cin >> s.first >> s.second >> g.first >> g.second;
	s.first--;s.second--;g.first--;g.second--;
	int grid[r][c];
	set < int > hor[r] , ver[c];
	for(int i = 0;i<r;i++){//1 = # , 0 = .
		string str;cin >> str;
		for(int j = 0;j<c;j++){
			grid[i][j] = str[j] == '#';
			if(i != s.first or j != s.second){
				ver[j].insert(i);
				hor[i].insert(j);
			}
		}
	}
	queue < pair < int , int > > bfs[r+c+1];
	bfs[0].push(s);
	int vis[r][c];
	memset(vis , 0 , sizeof(vis));
	for(int curdist = 0;;curdist++){
		while(bfs[curdist].size()){
			pair < int , int > p = bfs[curdist].front();
			bfs[curdist].pop();
			if(vis[p.first][p.second])continue;
			//cout << "bfs : " << p.first << " " << p.second << " " << dist << endl;
			vis[p.first][p.second] = 1;
			if(p == g){
				cout << curdist << '\n';
				return;
			}
			//spread
			if((p.first+n) < r){//	({n,-n} , {n,n})
				auto lb = hor[p.first + n].upper_bound(p.second - n);
				auto ub = hor[p.first + n].lower_bound(p.second + n);
				if(lb != hor[p.first + n].end() and ub != hor[p.first + n].begin()){
					vector < int > willdel;
					for(auto it = lb;it != ub;++it){
						willdel.push_back(*it);
					}
					for(auto itr : willdel){
						if(vis[p.first+n][itr] == 0){
							bfs[curdist+1].push({p.first + n , itr});
							hor[p.first + n].extract(itr);
							ver[itr].extract(p.first + n);
						}
					}
				}
			}
			if((p.first - n) >= 0){//	({-n,-n} , {-n,n})
				auto lb = hor[p.first - n].upper_bound(p.second - n);
				auto ub = hor[p.first - n].lower_bound(p.second + n);
				if(lb != hor[p.first - n].end() and ub != hor[p.first - n].begin()){
					vector < int > willdel;
					for(auto it = lb;it != ub;++it){
						willdel.push_back(*it);
					}
					for(auto itr : willdel){
						if(vis[p.first-n][itr] == 0){
							bfs[curdist+1].push({p.first - n , itr});
							hor[p.first - n].extract(itr);
							ver[itr].extract(p.first - n);
						}
					}
				}
			}
			if((p.second + n) < c){//	({-n,n} , {n,n})
				auto lb = ver[p.second + n].upper_bound(p.first - n);
				auto ub = ver[p.second + n].lower_bound(p.first + n);
				if(lb != ver[p.second + n].end() and ub != ver[p.second + n].begin()){
					vector < int > willdel;
					for(auto it = lb;it != ub;++it){
						willdel.push_back(*it);
					}
					for(auto itr : willdel){
						if(vis[itr][p.second + n]){
							bfs[curdist+1].push({itr , p.second + n});
							ver[p.second + n].extract(itr);
							hor[itr].extract(p.second + n);
						}
					}
				}
			}
			if((p.second - n) >= 0){//	({-n,-n} , {n,-n})
				auto lb = ver[p.second - n].upper_bound(p.first - n);
				auto ub = ver[p.second - n].lower_bound(p.first + n);
				if(lb != ver[p.second - n].end() and ub != ver[p.second - n].begin()){
					vector < int > willdel;
					for(auto it = lb;it != ub;++it){
						willdel.push_back(*it);
					}
					for(auto itr : willdel){
						if(vis[itr][p.second - n] == 0){
							bfs[curdist+1].push({itr , p.second - n,});
							ver[p.second - n].extract(itr);
							hor[itr].extract(p.second - n);
						}
					}
				}
			}
			if(p.first != 0 and grid[p.first-1][p.second] == 0 and vis[p.first-1][p.second] == 0)bfs[curdist].push({p.first-1,p.second});
			if(p.second != 0 and grid[p.first][p.second-1] == 0 and vis[p.first][p.second-1] == 0)bfs[curdist].push({p.first,p.second-1});
			if(p.first != (r-1) and grid[p.first+1][p.second] == 0 and vis[p.first+1][p.second] == 0)bfs[curdist].push({p.first+1,p.second});
			if(p.second != (c-1) and grid[p.first][p.second+1] == 0 and vis[p.first][p.second+1] == 0)bfs[curdist].push({p.first,p.second+1});
			if((abs(g.first - p.first) <= n and abs(g.second - p.second) <= (n-1)) or (abs(g.first - p.first) <= (n-1) and abs(g.second - p.second) <= n)){
				bfs[curdist+1].push(g);
			}
		}
	}
	cout << -1 << '\n';
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
}

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