Submission #936594

#	Time	Username	Problem	Language	Result	Execution time	Memory
936594		penguin133	Maze (JOI23_ho_t3)	C++17	19 / 100	1020 ms	615708 KiB

Main

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

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector <pi> adj[10000005];
int cnt, n, q;
struct node{
	int s, e, m;
	int nd, nd2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		nd = cnt++;
		nd2 = cnt++;
		if(s == e){
			adj[s].push_back({nd2, 0});
			adj[nd].push_back({s, 0});
		}
		else{
			l = new node(s, m);
			r = new node(m+1, e);
			adj[nd].push_back({l->nd, 0});
			adj[nd].push_back({r->nd, 0});
			adj[r->nd2].push_back({nd2, 0});
			adj[l->nd2].push_back({nd2, 0});
		}
	}
	
	void upd(int a, int b, int u, int v){
		if(s == a && b == e){
			adj[u].push_back({nd, v});
			return;
		}
		if(b <= m)l->upd(a, b, u, v);
		else if(a > m)r->upd(a, b, u, v);
		else l->upd(a, m, u, v), r->upd(m+1, b, u, v);
	}
	
	void upd2(int a, int b, int u, int v){
		if(s == a && b == e){
			adj[nd2].push_back({u, v});
			return;
		}
		if(b <= m)l->upd2(a, b, u, v);
		else if(a > m)r->upd2(a, b, u, v);
		else l->upd2(a, m, u, v), r->upd2(m+1, b, u, v);
	}
	
}*root;

char A[6000005]; int r, c;
inline int conv(int x, int y){
	return (x - 1) * c + y;
}

int ptr[10000005];
int dist[10000005];

void solve(){
	cin >> r >> c >> n;
	int a, b, cc, d; cin >> a >> b >> cc >> d;
	
	cnt = r * c + 1;
	root = new node(1, r * c);
	if(r > c){
		for(int i = 1; i <= r; i++){
			for(int j = 1; j <= c; j++)cin >> A[conv(j, i)];
		}
		swap(r, c);
	}
	else for(int i = 1; i <= r; i++)for(int j = 1; j <= c; j++)cin >> A[conv(i, j)];
	for(int i = 1; i <= r * c; i++){
		if(i > c && A[i - c] == '.')adj[i].push_back({i - c, 0});
		if(i <= c * (r - 1) && A[i + c] == '.')adj[i].push_back({i + c, 0});
		if(i % c != 1 && A[i - 1] == '.')adj[i].push_back({i - 1, 0});
		if(i % c && A[i + 1] == '.')adj[i].push_back({i + 1, 0});
		int aaa = (i - 1) / c + 1, bbb = (i - 1) % c + 1;
		for(int j = max(-n, -aaa + 1); j <= min(n, r - aaa); j++){
			if((i - 1) / c + 1 + j <= 0 || (i - 1) / c + 1 + j > r)continue;
			if(j == -n || j == n){
				int lft = max(1, bbb - n + 1);
				int rgt = min(c, bbb + n - 1);
				root->upd(conv(aaa + j, lft), conv(aaa + j, rgt), i, 1);
			}
			else{
				int lft = max(1, bbb - n);
				int rgt = min(c, bbb + n);
				root->upd(conv(aaa + j, lft), conv(aaa + j, rgt), i, 1);
			}
		}
	}
	for(int i = 1; i <= cnt; i++)dist[i] = 2e9;
	dist[conv(a, b)] = 0;
	//for(auto [i, j] : adj[conv(a, b)])cout << i << ' ' << j << '\n';
	deque <int> dq;
	const int os = (int)5e6;
	ptr[os] = conv(a, b);
	int cur = os - 1, cur2 = os;
	//dq.push_back(conv(a, b));
	while(1){
		//int x = dq.front(); dq.pop_front();
		int x = ptr[++cur];
		if(cur > cur2)break;
		for(auto [i, j] : adj[x]){
			if(dist[i] > dist[x] + j){
				dist[i] = dist[x] + j;
				//if(j)dq.push_back(i);
				//else dq.push_front(i);
				if(j)ptr[cur--] = i;
				else ptr[++cur2] = i;
			}
		}
	}
	//for(int i = 1; i <= cnt; i++)cout << dist[i] << ' ';
	cout << dist[conv(cc, d)];
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

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

• Subtask 1: 0 / 8
• Subtask 2: 19 / 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