oj.uz

Submission #936588

# Submission time Handle Problem Language Result Execution time Memory
936588 2024-03-02T09:24:12 Z penguin133 Maze (JOI23_ho_t3) C++17
19 / 100
 2000 ms 955628 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[6000005];
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 dist[6000005];

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});
		for(int j = -n; j <= n; j++){
			if((i - 1) / c + 1 + j <= 0 || (i - 1) / c + 1 + j > r)continue;
			if(j == -n || j == n){
				int lft = max(1ll, (i - 1) % c + 1 - n + 1);
				int rgt = min(c, (i - 1) % c + 1 + n - 1);
				root->upd(conv((i - 1) / c + 1 + j, lft), conv((i - 1) / c + j + 1, rgt), i, 1);
			}
			else{
				int lft = max(1ll, (i - 1) % c + 1 - n);
				int rgt = min(c, (i - 1) % c + 1 + n);
				cerr << i << ' ' << j << ' ' << lft << ' ' << rgt << '\n';
				root->upd(conv((i - 1) / c + 1 + j, lft), conv((i - 1) / c + j + 1, rgt), i, 1);
			}
		}
	}
	for(int i = 1; i <= cnt; i++)dist[i] = 1e18;
	dist[conv(a, b)] = 0;
	//for(auto [i, j] : adj[conv(a, b)])cout << i << ' ' << j << '\n';
	deque <int> dq;
	dq.push_back(conv(a, b));
	while(!dq.empty()){
		int x = dq.front(); dq.pop_front();
		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);
			}
		}
	}
	//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:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 | main(){
      | ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 144724 KB Output is correct
2 Correct 34 ms 144720 KB Output is correct
3 Correct 45 ms 145232 KB Output is correct
4 Correct 50 ms 145292 KB Output is correct
5 Correct 43 ms 145232 KB Output is correct
6 Correct 44 ms 145236 KB Output is correct
7 Correct 47 ms 145016 KB Output is correct
8 Correct 46 ms 145292 KB Output is correct
9 Correct 35 ms 144980 KB Output is correct
10 Correct 36 ms 144732 KB Output is correct
11 Correct 34 ms 144680 KB Output is correct
12 Correct 35 ms 144564 KB Output is correct
13 Correct 38 ms 144732 KB Output is correct
14 Correct 38 ms 144836 KB Output is correct
15 Correct 35 ms 144748 KB Output is correct
16 Correct 44 ms 145260 KB Output is correct
17 Correct 48 ms 145244 KB Output is correct
18 Correct 44 ms 145072 KB Output is correct
19 Correct 636 ms 175952 KB Output is correct
20 Correct 474 ms 164692 KB Output is correct
21 Correct 641 ms 183528 KB Output is correct
22 Correct 649 ms 176572 KB Output is correct
23 Correct 632 ms 175892 KB Output is correct
24 Correct 639 ms 176388 KB Output is correct
25 Correct 606 ms 172584 KB Output is correct
26 Correct 664 ms 176824 KB Output is correct
27 Correct 645 ms 176472 KB Output is correct
28 Correct 626 ms 175968 KB Output is correct
29 Correct 1548 ms 218204 KB Output is correct
30 Correct 626 ms 176044 KB Output is correct
31 Correct 1552 ms 236768 KB Output is correct
32 Correct 1519 ms 220348 KB Output is correct
33 Correct 1499 ms 218084 KB Output is correct
34 Correct 1481 ms 218772 KB Output is correct
35 Correct 1458 ms 209928 KB Output is correct
36 Correct 1567 ms 221176 KB Output is correct
37 Correct 1554 ms 220128 KB Output is correct
38 Correct 1548 ms 218240 KB Output is correct
39 Runtime error 784 ms 955628 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 144732 KB Output is correct
2 Correct 35 ms 144728 KB Output is correct
3 Correct 38 ms 144732 KB Output is correct
4 Correct 34 ms 144732 KB Output is correct
5 Correct 43 ms 145236 KB Output is correct
6 Correct 36 ms 145380 KB Output is correct
7 Correct 38 ms 144732 KB Output is correct
8 Correct 42 ms 144860 KB Output is correct
9 Correct 46 ms 145220 KB Output is correct
10 Correct 45 ms 145236 KB Output is correct
11 Correct 44 ms 145068 KB Output is correct
12 Correct 319 ms 149420 KB Output is correct
13 Correct 309 ms 149588 KB Output is correct
14 Correct 317 ms 149796 KB Output is correct
15 Correct 43 ms 145080 KB Output is correct
16 Correct 43 ms 144984 KB Output is correct
17 Correct 52 ms 145232 KB Output is correct
18 Correct 34 ms 144728 KB Output is correct
19 Correct 88 ms 145736 KB Output is correct
20 Correct 44 ms 144724 KB Output is correct
21 Correct 35 ms 144772 KB Output is correct
22 Correct 66 ms 145232 KB Output is correct
23 Correct 45 ms 144728 KB Output is correct
24 Correct 35 ms 144720 KB Output is correct
25 Correct 34 ms 144720 KB Output is correct
26 Correct 35 ms 144812 KB Output is correct
27 Correct 36 ms 144724 KB Output is correct
28 Correct 54 ms 145236 KB Output is correct
29 Correct 35 ms 144788 KB Output is correct
30 Correct 48 ms 145236 KB Output is correct
31 Correct 43 ms 145232 KB Output is correct
32 Correct 44 ms 145232 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 144728 KB Output is correct
2 Correct 34 ms 144732 KB Output is correct
3 Correct 36 ms 144728 KB Output is correct
4 Correct 34 ms 144544 KB Output is correct
5 Correct 33 ms 144724 KB Output is correct
6 Correct 37 ms 144828 KB Output is correct
7 Correct 44 ms 145236 KB Output is correct
8 Correct 43 ms 145236 KB Output is correct
9 Correct 299 ms 149276 KB Output is correct
10 Correct 322 ms 149328 KB Output is correct
11 Correct 318 ms 149328 KB Output is correct
12 Correct 44 ms 145424 KB Output is correct
13 Correct 35 ms 144544 KB Output is correct
14 Correct 88 ms 145748 KB Output is correct
15 Correct 35 ms 144724 KB Output is correct
16 Correct 69 ms 145360 KB Output is correct
17 Correct 44 ms 144976 KB Output is correct
18 Correct 34 ms 144720 KB Output is correct
19 Correct 34 ms 144748 KB Output is correct
20 Correct 36 ms 144840 KB Output is correct
21 Correct 54 ms 145152 KB Output is correct
22 Correct 43 ms 145232 KB Output is correct
23 Correct 45 ms 145248 KB Output is correct
24 Correct 612 ms 153680 KB Output is correct
25 Correct 1745 ms 179364 KB Output is correct
26 Execution timed out 2029 ms 188492 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 144732 KB Output is correct
2 Correct 35 ms 144728 KB Output is correct
3 Correct 38 ms 144732 KB Output is correct
4 Correct 34 ms 144732 KB Output is correct
5 Correct 43 ms 145236 KB Output is correct
6 Correct 36 ms 145380 KB Output is correct
7 Correct 38 ms 144732 KB Output is correct
8 Correct 42 ms 144860 KB Output is correct
9 Correct 46 ms 145220 KB Output is correct
10 Correct 45 ms 145236 KB Output is correct
11 Correct 44 ms 145068 KB Output is correct
12 Correct 319 ms 149420 KB Output is correct
13 Correct 309 ms 149588 KB Output is correct
14 Correct 317 ms 149796 KB Output is correct
15 Correct 43 ms 145080 KB Output is correct
16 Correct 43 ms 144984 KB Output is correct
17 Correct 52 ms 145232 KB Output is correct
18 Correct 34 ms 144728 KB Output is correct
19 Correct 88 ms 145736 KB Output is correct
20 Correct 44 ms 144724 KB Output is correct
21 Correct 35 ms 144772 KB Output is correct
22 Correct 66 ms 145232 KB Output is correct
23 Correct 45 ms 144728 KB Output is correct
24 Correct 35 ms 144720 KB Output is correct
25 Correct 34 ms 144720 KB Output is correct
26 Correct 35 ms 144812 KB Output is correct
27 Correct 36 ms 144724 KB Output is correct
28 Correct 54 ms 145236 KB Output is correct
29 Correct 35 ms 144788 KB Output is correct
30 Correct 48 ms 145236 KB Output is correct
31 Correct 43 ms 145232 KB Output is correct
32 Correct 44 ms 145232 KB Output is correct
33 Correct 663 ms 171776 KB Output is correct
34 Correct 589 ms 151568 KB Output is correct
35 Correct 147 ms 144976 KB Output is correct
36 Correct 1799 ms 177604 KB Output is correct
37 Correct 492 ms 162360 KB Output is correct
38 Execution timed out 2056 ms 186384 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 144732 KB Output is correct
2 Correct 35 ms 144728 KB Output is correct
3 Correct 38 ms 144732 KB Output is correct
4 Correct 34 ms 144732 KB Output is correct
5 Correct 43 ms 145236 KB Output is correct
6 Correct 36 ms 145380 KB Output is correct
7 Correct 38 ms 144732 KB Output is correct
8 Correct 42 ms 144860 KB Output is correct
9 Correct 46 ms 145220 KB Output is correct
10 Correct 45 ms 145236 KB Output is correct
11 Correct 44 ms 145068 KB Output is correct
12 Correct 319 ms 149420 KB Output is correct
13 Correct 309 ms 149588 KB Output is correct
14 Correct 317 ms 149796 KB Output is correct
15 Correct 43 ms 145080 KB Output is correct
16 Correct 43 ms 144984 KB Output is correct
17 Correct 52 ms 145232 KB Output is correct
18 Correct 34 ms 144728 KB Output is correct
19 Correct 88 ms 145736 KB Output is correct
20 Correct 44 ms 144724 KB Output is correct
21 Correct 35 ms 144772 KB Output is correct
22 Correct 66 ms 145232 KB Output is correct
23 Correct 45 ms 144728 KB Output is correct
24 Correct 35 ms 144720 KB Output is correct
25 Correct 34 ms 144720 KB Output is correct
26 Correct 35 ms 144812 KB Output is correct
27 Correct 36 ms 144724 KB Output is correct
28 Correct 54 ms 145236 KB Output is correct
29 Correct 35 ms 144788 KB Output is correct
30 Correct 48 ms 145236 KB Output is correct
31 Correct 43 ms 145232 KB Output is correct
32 Correct 44 ms 145232 KB Output is correct
33 Correct 663 ms 171776 KB Output is correct
34 Correct 589 ms 151568 KB Output is correct
35 Correct 147 ms 144976 KB Output is correct
36 Correct 1799 ms 177604 KB Output is correct
37 Correct 492 ms 162360 KB Output is correct
38 Execution timed out 2056 ms 186384 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 144724 KB Output is correct
2 Correct 34 ms 144720 KB Output is correct
3 Correct 45 ms 145232 KB Output is correct
4 Correct 50 ms 145292 KB Output is correct
5 Correct 43 ms 145232 KB Output is correct
6 Correct 44 ms 145236 KB Output is correct
7 Correct 47 ms 145016 KB Output is correct
8 Correct 46 ms 145292 KB Output is correct
9 Correct 35 ms 144980 KB Output is correct
10 Correct 36 ms 144732 KB Output is correct
11 Correct 34 ms 144680 KB Output is correct
12 Correct 35 ms 144564 KB Output is correct
13 Correct 38 ms 144732 KB Output is correct
14 Correct 38 ms 144836 KB Output is correct
15 Correct 35 ms 144748 KB Output is correct
16 Correct 44 ms 145260 KB Output is correct
17 Correct 48 ms 145244 KB Output is correct
18 Correct 44 ms 145072 KB Output is correct
19 Correct 636 ms 175952 KB Output is correct
20 Correct 474 ms 164692 KB Output is correct
21 Correct 641 ms 183528 KB Output is correct
22 Correct 649 ms 176572 KB Output is correct
23 Correct 632 ms 175892 KB Output is correct
24 Correct 639 ms 176388 KB Output is correct
25 Correct 606 ms 172584 KB Output is correct
26 Correct 664 ms 176824 KB Output is correct
27 Correct 645 ms 176472 KB Output is correct
28 Correct 626 ms 175968 KB Output is correct
29 Correct 1548 ms 218204 KB Output is correct
30 Correct 626 ms 176044 KB Output is correct
31 Correct 1552 ms 236768 KB Output is correct
32 Correct 1519 ms 220348 KB Output is correct
33 Correct 1499 ms 218084 KB Output is correct
34 Correct 1481 ms 218772 KB Output is correct
35 Correct 1458 ms 209928 KB Output is correct
36 Correct 1567 ms 221176 KB Output is correct
37 Correct 1554 ms 220128 KB Output is correct
38 Correct 1548 ms 218240 KB Output is correct
39 Runtime error 784 ms 955628 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 144724 KB Output is correct
2 Correct 34 ms 144720 KB Output is correct
3 Correct 45 ms 145232 KB Output is correct
4 Correct 50 ms 145292 KB Output is correct
5 Correct 43 ms 145232 KB Output is correct
6 Correct 44 ms 145236 KB Output is correct
7 Correct 47 ms 145016 KB Output is correct
8 Correct 46 ms 145292 KB Output is correct
9 Correct 35 ms 144980 KB Output is correct
10 Correct 36 ms 144732 KB Output is correct
11 Correct 34 ms 144680 KB Output is correct
12 Correct 35 ms 144564 KB Output is correct
13 Correct 38 ms 144732 KB Output is correct
14 Correct 38 ms 144836 KB Output is correct
15 Correct 35 ms 144748 KB Output is correct
16 Correct 44 ms 145260 KB Output is correct
17 Correct 48 ms 145244 KB Output is correct
18 Correct 44 ms 145072 KB Output is correct
19 Correct 636 ms 175952 KB Output is correct
20 Correct 474 ms 164692 KB Output is correct
21 Correct 641 ms 183528 KB Output is correct
22 Correct 649 ms 176572 KB Output is correct
23 Correct 632 ms 175892 KB Output is correct
24 Correct 639 ms 176388 KB Output is correct
25 Correct 606 ms 172584 KB Output is correct
26 Correct 664 ms 176824 KB Output is correct
27 Correct 645 ms 176472 KB Output is correct
28 Correct 626 ms 175968 KB Output is correct
29 Correct 1548 ms 218204 KB Output is correct
30 Correct 626 ms 176044 KB Output is correct
31 Correct 1552 ms 236768 KB Output is correct
32 Correct 1519 ms 220348 KB Output is correct
33 Correct 1499 ms 218084 KB Output is correct
34 Correct 1481 ms 218772 KB Output is correct
35 Correct 1458 ms 209928 KB Output is correct
36 Correct 1567 ms 221176 KB Output is correct
37 Correct 1554 ms 220128 KB Output is correct
38 Correct 1548 ms 218240 KB Output is correct
39 Runtime error 784 ms 955628 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 144724 KB Output is correct
2 Correct 34 ms 144720 KB Output is correct
3 Correct 45 ms 145232 KB Output is correct
4 Correct 50 ms 145292 KB Output is correct
5 Correct 43 ms 145232 KB Output is correct
6 Correct 44 ms 145236 KB Output is correct
7 Correct 47 ms 145016 KB Output is correct
8 Correct 46 ms 145292 KB Output is correct
9 Correct 35 ms 144980 KB Output is correct
10 Correct 36 ms 144732 KB Output is correct
11 Correct 34 ms 144680 KB Output is correct
12 Correct 35 ms 144564 KB Output is correct
13 Correct 38 ms 144732 KB Output is correct
14 Correct 38 ms 144836 KB Output is correct
15 Correct 35 ms 144748 KB Output is correct
16 Correct 44 ms 145260 KB Output is correct
17 Correct 48 ms 145244 KB Output is correct
18 Correct 44 ms 145072 KB Output is correct
19 Correct 636 ms 175952 KB Output is correct
20 Correct 474 ms 164692 KB Output is correct
21 Correct 641 ms 183528 KB Output is correct
22 Correct 649 ms 176572 KB Output is correct
23 Correct 632 ms 175892 KB Output is correct
24 Correct 639 ms 176388 KB Output is correct
25 Correct 606 ms 172584 KB Output is correct
26 Correct 664 ms 176824 KB Output is correct
27 Correct 645 ms 176472 KB Output is correct
28 Correct 626 ms 175968 KB Output is correct
29 Correct 1548 ms 218204 KB Output is correct
30 Correct 626 ms 176044 KB Output is correct
31 Correct 1552 ms 236768 KB Output is correct
32 Correct 1519 ms 220348 KB Output is correct
33 Correct 1499 ms 218084 KB Output is correct
34 Correct 1481 ms 218772 KB Output is correct
35 Correct 1458 ms 209928 KB Output is correct
36 Correct 1567 ms 221176 KB Output is correct
37 Correct 1554 ms 220128 KB Output is correct
38 Correct 1548 ms 218240 KB Output is correct
39 Runtime error 784 ms 955628 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -