Submission #860571

#	Time	Username	Problem	Language	Result	Execution time	Memory
860571		NotLinux	Maze (JOI23_ho_t3)	C++17	51 / 100	2081 ms	1146904 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int r,c,n;
struct DSU{
	vector < vector < pair < int , int > > > par,reel;
	vector < vector < int > > sz;
	DSU(int x , int y){
		par.assign(x+1 , vector < pair < int , int > > (y+1));
		sz.assign(x+1 , vector < int > (y+1,1));
		reel.assign(x+1 , vector < pair < int , int > > (y+1));
		for(int i = 0;i<=x;i++)for(int j = 0;j<=y;j++){
			par[i][j] = {i,j};
			reel[i][j] = {i,j};
		}
	}
	inline pair < int , int > rfind(pair < int , int > a){
		pair < int , int > ret = find(a);
		return reel[ret.first][ret.second];
	}
	inline pair < int , int > find(pair < int , int > a){
		if(a.first < 0)a.first = 0;
		if(a.first >= r)a.first = r-1;
		if(a.second < 0)a.second = 0;
		if(a.second >= c)a.second = c-1;
		if(par[a.first][a.second] == a){
			//cout << a.first << " " << a.second << " -> " << par[a.first][a.second].first << " " << par[a.first][a.second].second << endl;
			return a;
		}
		par[a.first][a.second] = find(par[a.first][a.second]);
		//cout << a.first << " " << a.second << " -> " << par[a.first][a.second].first << " " << par[a.first][a.second].second << endl;
		return par[a.first][a.second];
	}
	inline void merge(pair < int , int > a , pair < int , int > b){//a < b
		//cout << "merge : " << a.first << "," << a.second << "   " << b.first << "," << b.second << endl;
		if(find(a) == find(b))return;
		pair < int , int > fa = find(a);
		pair < int , int > fb = find(b);
		/*cout << "find(" << a.first << "," << a.second << ") = " << fa.first << " " << fa.second << endl;
		cout << "find(" << b.first << "," << b.second << ") = " << fb.first << " " << fb.second << endl;
		cout << "sz : " << sz[fa.first][fa.second] << " , " << sz[fb.first][fb.second] << endl;*/
		if(sz[fa.first][fa.second] > sz[fb.first][fb.second]){
			swap(reel[fa.first][fa.second] , reel[fb.first][fb.second]);
			swap(a,b);
			swap(fa,fb);
		}
		sz[fb.first][fb.second] += sz[fa.first][fa.second];
		par[fa.first][fa.second] = fb;
		//cout << "parent is : " << fb.first << " " << fb.second << " , " << reel[fb.first][fb.second].first << " " << reel[fb.first][fb.second].second << endl;
	}
};
void solve(){
	cin >> r >> c >> n;
	DSU dsuhor(r,c) , dsuver(r,c);
	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];
	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] == '#';
		}
	}
	queue < pair < int , int > > bfs[r+c+1];
	bfs[0].push(s);
	vector < vector < int > > vis(r , vector < int > (c,0));
	for(int curdist = 0;curdist < (r+c+1);curdist++){
		while(bfs[curdist].size()){
			pair < int , int > p = bfs[curdist].front();
			bfs[curdist].pop();
			if(p == g){
				cout << curdist << '\n';
				return;
			}
			if(vis[p.first][p.second])continue;
			vis[p.first][p.second] = 1;
			dsuhor.merge(p,{p.first,p.second+1});
			dsuver.merge(p,{p.first+1,p.second});
			if((p.first + n) < r){//	({n,-n} , {n,n})
				pair < int , int > dfs = dsuhor.rfind({p.first + n , p.second - n + 1});
				while(dfs.second < (p.second + n)){
					bfs[curdist+1].push(dfs);
					if(dfs.second == (c-1))break;
					dfs = dsuhor.rfind({dfs.first , dfs.second+1});
				}
			}
			if((p.first - n) >= 0){//	({-n,-n} , {-n,n})
				pair < int , int > dfs = dsuhor.rfind({p.first - n , p.second - n + 1});
				while(dfs.second < (p.second + n)){
					bfs[curdist+1].push(dfs);
					if(dfs.second == (c-1))break;
					dfs = dsuhor.rfind({dfs.first , dfs.second+1});
				}	
			}
			if((p.second + n) < c){//	({-n,n} , {n,n})
				pair < int , int > dfs = dsuver.rfind({p.first - n + 1, p.second + n});
				while(dfs.first < (p.first + n)){
					bfs[curdist+1].push(dfs);
					if(dfs.first == (r-1))break;
					dfs = dsuver.rfind({dfs.first+1 , dfs.second});
				}	
			}
			if((p.second - n) >= 0){//	({-n,-n} , {n,-n})
				pair < int , int > dfs = dsuver.rfind({p.first - n + 1, p.second - n});
				while(dfs.first < (p.first + n)){
					bfs[curdist+1].push(dfs);
					if(dfs.first == (r-1))break;
					dfs = dsuver.rfind({dfs.first+1 , dfs.second});
				}	
			}
			if(p.first != 0 and grid[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){
				bfs[curdist].push({p.first,p.second-1});
			}
			if(p.first != (r-1) and grid[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){
				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: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6