oj.uz

Submission #936594

# Submission time Handle Problem Language Result Execution time Memory
936594 2024-03-02T09:38:08 Z penguin133 Maze (JOI23_ho_t3) C++17
19 / 100
 1020 ms 615708 KB 
#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

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 241232 KB Output is correct
2 Correct 55 ms 241232 KB Output is correct
3 Correct 57 ms 241488 KB Output is correct
4 Correct 55 ms 241488 KB Output is correct
5 Correct 57 ms 241492 KB Output is correct
6 Correct 56 ms 241612 KB Output is correct
7 Correct 55 ms 241496 KB Output is correct
8 Correct 56 ms 241488 KB Output is correct
9 Correct 55 ms 241264 KB Output is correct
10 Correct 57 ms 241236 KB Output is correct
11 Correct 58 ms 241248 KB Output is correct
12 Correct 56 ms 241240 KB Output is correct
13 Correct 55 ms 241232 KB Output is correct
14 Correct 57 ms 241128 KB Output is correct
15 Correct 56 ms 241280 KB Output is correct
16 Correct 56 ms 241488 KB Output is correct
17 Correct 56 ms 241504 KB Output is correct
18 Correct 56 ms 241476 KB Output is correct
19 Correct 127 ms 264844 KB Output is correct
20 Correct 87 ms 256516 KB Output is correct
21 Correct 111 ms 266324 KB Output is correct
22 Correct 162 ms 269176 KB Output is correct
23 Correct 113 ms 264788 KB Output is correct
24 Correct 94 ms 263000 KB Output is correct
25 Correct 95 ms 261092 KB Output is correct
26 Correct 221 ms 275540 KB Output is correct
27 Correct 209 ms 275580 KB Output is correct
28 Correct 138 ms 266904 KB Output is correct
29 Correct 238 ms 302516 KB Output is correct
30 Runtime error 425 ms 575028 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 241232 KB Output is correct
2 Correct 55 ms 241132 KB Output is correct
3 Correct 55 ms 241292 KB Output is correct
4 Correct 58 ms 241180 KB Output is correct
5 Correct 56 ms 241596 KB Output is correct
6 Correct 56 ms 241232 KB Output is correct
7 Correct 57 ms 241236 KB Output is correct
8 Correct 54 ms 241136 KB Output is correct
9 Correct 56 ms 241668 KB Output is correct
10 Correct 56 ms 241584 KB Output is correct
11 Correct 56 ms 241612 KB Output is correct
12 Correct 60 ms 243492 KB Output is correct
13 Correct 59 ms 243544 KB Output is correct
14 Correct 61 ms 243540 KB Output is correct
15 Correct 56 ms 241492 KB Output is correct
16 Correct 57 ms 241492 KB Output is correct
17 Correct 57 ms 241412 KB Output is correct
18 Correct 60 ms 241148 KB Output is correct
19 Correct 56 ms 241756 KB Output is correct
20 Correct 55 ms 241232 KB Output is correct
21 Correct 58 ms 241492 KB Output is correct
22 Correct 56 ms 241600 KB Output is correct
23 Correct 55 ms 241368 KB Output is correct
24 Correct 55 ms 241212 KB Output is correct
25 Correct 57 ms 241232 KB Output is correct
26 Correct 55 ms 241232 KB Output is correct
27 Correct 55 ms 241256 KB Output is correct
28 Correct 57 ms 241500 KB Output is correct
29 Correct 55 ms 241084 KB Output is correct
30 Correct 56 ms 241504 KB Output is correct
31 Correct 57 ms 241612 KB Output is correct
32 Correct 55 ms 241460 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 241232 KB Output is correct
2 Correct 54 ms 241232 KB Output is correct
3 Correct 55 ms 241236 KB Output is correct
4 Correct 55 ms 241280 KB Output is correct
5 Correct 55 ms 241232 KB Output is correct
6 Correct 58 ms 241488 KB Output is correct
7 Correct 56 ms 241500 KB Output is correct
8 Correct 56 ms 241488 KB Output is correct
9 Correct 60 ms 243316 KB Output is correct
10 Correct 60 ms 243540 KB Output is correct
11 Correct 61 ms 243384 KB Output is correct
12 Correct 55 ms 241488 KB Output is correct
13 Correct 56 ms 241232 KB Output is correct
14 Correct 62 ms 241824 KB Output is correct
15 Correct 55 ms 241236 KB Output is correct
16 Correct 57 ms 241488 KB Output is correct
17 Correct 57 ms 241376 KB Output is correct
18 Correct 55 ms 241232 KB Output is correct
19 Correct 56 ms 241092 KB Output is correct
20 Correct 55 ms 241244 KB Output is correct
21 Correct 55 ms 241492 KB Output is correct
22 Correct 58 ms 241488 KB Output is correct
23 Correct 56 ms 241548 KB Output is correct
24 Correct 66 ms 245332 KB Output is correct
25 Correct 192 ms 272976 KB Output is correct
26 Runtime error 998 ms 615576 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 241232 KB Output is correct
2 Correct 55 ms 241132 KB Output is correct
3 Correct 55 ms 241292 KB Output is correct
4 Correct 58 ms 241180 KB Output is correct
5 Correct 56 ms 241596 KB Output is correct
6 Correct 56 ms 241232 KB Output is correct
7 Correct 57 ms 241236 KB Output is correct
8 Correct 54 ms 241136 KB Output is correct
9 Correct 56 ms 241668 KB Output is correct
10 Correct 56 ms 241584 KB Output is correct
11 Correct 56 ms 241612 KB Output is correct
12 Correct 60 ms 243492 KB Output is correct
13 Correct 59 ms 243544 KB Output is correct
14 Correct 61 ms 243540 KB Output is correct
15 Correct 56 ms 241492 KB Output is correct
16 Correct 57 ms 241492 KB Output is correct
17 Correct 57 ms 241412 KB Output is correct
18 Correct 60 ms 241148 KB Output is correct
19 Correct 56 ms 241756 KB Output is correct
20 Correct 55 ms 241232 KB Output is correct
21 Correct 58 ms 241492 KB Output is correct
22 Correct 56 ms 241600 KB Output is correct
23 Correct 55 ms 241368 KB Output is correct
24 Correct 55 ms 241212 KB Output is correct
25 Correct 57 ms 241232 KB Output is correct
26 Correct 55 ms 241232 KB Output is correct
27 Correct 55 ms 241256 KB Output is correct
28 Correct 57 ms 241500 KB Output is correct
29 Correct 55 ms 241084 KB Output is correct
30 Correct 56 ms 241504 KB Output is correct
31 Correct 57 ms 241612 KB Output is correct
32 Correct 55 ms 241460 KB Output is correct
33 Correct 122 ms 265052 KB Output is correct
34 Correct 66 ms 245332 KB Output is correct
35 Correct 67 ms 244820 KB Output is correct
36 Correct 199 ms 272976 KB Output is correct
37 Correct 84 ms 256660 KB Output is correct
38 Runtime error 1020 ms 615708 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 241232 KB Output is correct
2 Correct 55 ms 241132 KB Output is correct
3 Correct 55 ms 241292 KB Output is correct
4 Correct 58 ms 241180 KB Output is correct
5 Correct 56 ms 241596 KB Output is correct
6 Correct 56 ms 241232 KB Output is correct
7 Correct 57 ms 241236 KB Output is correct
8 Correct 54 ms 241136 KB Output is correct
9 Correct 56 ms 241668 KB Output is correct
10 Correct 56 ms 241584 KB Output is correct
11 Correct 56 ms 241612 KB Output is correct
12 Correct 60 ms 243492 KB Output is correct
13 Correct 59 ms 243544 KB Output is correct
14 Correct 61 ms 243540 KB Output is correct
15 Correct 56 ms 241492 KB Output is correct
16 Correct 57 ms 241492 KB Output is correct
17 Correct 57 ms 241412 KB Output is correct
18 Correct 60 ms 241148 KB Output is correct
19 Correct 56 ms 241756 KB Output is correct
20 Correct 55 ms 241232 KB Output is correct
21 Correct 58 ms 241492 KB Output is correct
22 Correct 56 ms 241600 KB Output is correct
23 Correct 55 ms 241368 KB Output is correct
24 Correct 55 ms 241212 KB Output is correct
25 Correct 57 ms 241232 KB Output is correct
26 Correct 55 ms 241232 KB Output is correct
27 Correct 55 ms 241256 KB Output is correct
28 Correct 57 ms 241500 KB Output is correct
29 Correct 55 ms 241084 KB Output is correct
30 Correct 56 ms 241504 KB Output is correct
31 Correct 57 ms 241612 KB Output is correct
32 Correct 55 ms 241460 KB Output is correct
33 Correct 122 ms 265052 KB Output is correct
34 Correct 66 ms 245332 KB Output is correct
35 Correct 67 ms 244820 KB Output is correct
36 Correct 199 ms 272976 KB Output is correct
37 Correct 84 ms 256660 KB Output is correct
38 Runtime error 1020 ms 615708 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 241232 KB Output is correct
2 Correct 55 ms 241232 KB Output is correct
3 Correct 57 ms 241488 KB Output is correct
4 Correct 55 ms 241488 KB Output is correct
5 Correct 57 ms 241492 KB Output is correct
6 Correct 56 ms 241612 KB Output is correct
7 Correct 55 ms 241496 KB Output is correct
8 Correct 56 ms 241488 KB Output is correct
9 Correct 55 ms 241264 KB Output is correct
10 Correct 57 ms 241236 KB Output is correct
11 Correct 58 ms 241248 KB Output is correct
12 Correct 56 ms 241240 KB Output is correct
13 Correct 55 ms 241232 KB Output is correct
14 Correct 57 ms 241128 KB Output is correct
15 Correct 56 ms 241280 KB Output is correct
16 Correct 56 ms 241488 KB Output is correct
17 Correct 56 ms 241504 KB Output is correct
18 Correct 56 ms 241476 KB Output is correct
19 Correct 127 ms 264844 KB Output is correct
20 Correct 87 ms 256516 KB Output is correct
21 Correct 111 ms 266324 KB Output is correct
22 Correct 162 ms 269176 KB Output is correct
23 Correct 113 ms 264788 KB Output is correct
24 Correct 94 ms 263000 KB Output is correct
25 Correct 95 ms 261092 KB Output is correct
26 Correct 221 ms 275540 KB Output is correct
27 Correct 209 ms 275580 KB Output is correct
28 Correct 138 ms 266904 KB Output is correct
29 Correct 238 ms 302516 KB Output is correct
30 Runtime error 425 ms 575028 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 241232 KB Output is correct
2 Correct 55 ms 241232 KB Output is correct
3 Correct 57 ms 241488 KB Output is correct
4 Correct 55 ms 241488 KB Output is correct
5 Correct 57 ms 241492 KB Output is correct
6 Correct 56 ms 241612 KB Output is correct
7 Correct 55 ms 241496 KB Output is correct
8 Correct 56 ms 241488 KB Output is correct
9 Correct 55 ms 241264 KB Output is correct
10 Correct 57 ms 241236 KB Output is correct
11 Correct 58 ms 241248 KB Output is correct
12 Correct 56 ms 241240 KB Output is correct
13 Correct 55 ms 241232 KB Output is correct
14 Correct 57 ms 241128 KB Output is correct
15 Correct 56 ms 241280 KB Output is correct
16 Correct 56 ms 241488 KB Output is correct
17 Correct 56 ms 241504 KB Output is correct
18 Correct 56 ms 241476 KB Output is correct
19 Correct 127 ms 264844 KB Output is correct
20 Correct 87 ms 256516 KB Output is correct
21 Correct 111 ms 266324 KB Output is correct
22 Correct 162 ms 269176 KB Output is correct
23 Correct 113 ms 264788 KB Output is correct
24 Correct 94 ms 263000 KB Output is correct
25 Correct 95 ms 261092 KB Output is correct
26 Correct 221 ms 275540 KB Output is correct
27 Correct 209 ms 275580 KB Output is correct
28 Correct 138 ms 266904 KB Output is correct
29 Correct 238 ms 302516 KB Output is correct
30 Runtime error 425 ms 575028 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 241232 KB Output is correct
2 Correct 55 ms 241232 KB Output is correct
3 Correct 57 ms 241488 KB Output is correct
4 Correct 55 ms 241488 KB Output is correct
5 Correct 57 ms 241492 KB Output is correct
6 Correct 56 ms 241612 KB Output is correct
7 Correct 55 ms 241496 KB Output is correct
8 Correct 56 ms 241488 KB Output is correct
9 Correct 55 ms 241264 KB Output is correct
10 Correct 57 ms 241236 KB Output is correct
11 Correct 58 ms 241248 KB Output is correct
12 Correct 56 ms 241240 KB Output is correct
13 Correct 55 ms 241232 KB Output is correct
14 Correct 57 ms 241128 KB Output is correct
15 Correct 56 ms 241280 KB Output is correct
16 Correct 56 ms 241488 KB Output is correct
17 Correct 56 ms 241504 KB Output is correct
18 Correct 56 ms 241476 KB Output is correct
19 Correct 127 ms 264844 KB Output is correct
20 Correct 87 ms 256516 KB Output is correct
21 Correct 111 ms 266324 KB Output is correct
22 Correct 162 ms 269176 KB Output is correct
23 Correct 113 ms 264788 KB Output is correct
24 Correct 94 ms 263000 KB Output is correct
25 Correct 95 ms 261092 KB Output is correct
26 Correct 221 ms 275540 KB Output is correct
27 Correct 209 ms 275580 KB Output is correct
28 Correct 138 ms 266904 KB Output is correct
29 Correct 238 ms 302516 KB Output is correct
30 Runtime error 425 ms 575028 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -