oj.uz

Submission #936590

# Submission time Handle Problem Language Result Execution time Memory
936590 2024-03-02T09:26:32 Z penguin133 Maze (JOI23_ho_t3) C++17
19 / 100
 2000 ms 709444 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 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;
		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(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:120:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  120 | main(){
      | ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 237192 KB Output is correct
2 Correct 73 ms 237140 KB Output is correct
3 Correct 96 ms 237468 KB Output is correct
4 Correct 85 ms 237656 KB Output is correct
5 Correct 86 ms 237616 KB Output is correct
6 Correct 86 ms 237648 KB Output is correct
7 Correct 85 ms 237652 KB Output is correct
8 Correct 84 ms 237392 KB Output is correct
9 Correct 75 ms 237084 KB Output is correct
10 Correct 98 ms 237144 KB Output is correct
11 Correct 76 ms 236976 KB Output is correct
12 Correct 75 ms 237136 KB Output is correct
13 Correct 76 ms 237136 KB Output is correct
14 Correct 77 ms 237008 KB Output is correct
15 Correct 77 ms 237196 KB Output is correct
16 Correct 85 ms 237568 KB Output is correct
17 Correct 85 ms 237576 KB Output is correct
18 Correct 85 ms 237648 KB Output is correct
19 Correct 666 ms 266424 KB Output is correct
20 Correct 515 ms 256832 KB Output is correct
21 Correct 669 ms 274256 KB Output is correct
22 Correct 679 ms 266836 KB Output is correct
23 Correct 662 ms 266512 KB Output is correct
24 Correct 650 ms 266628 KB Output is correct
25 Correct 647 ms 262920 KB Output is correct
26 Correct 669 ms 267348 KB Output is correct
27 Correct 682 ms 266832 KB Output is correct
28 Correct 664 ms 266548 KB Output is correct
29 Correct 1590 ms 310488 KB Output is correct
30 Correct 667 ms 266712 KB Output is correct
31 Correct 1573 ms 328900 KB Output is correct
32 Correct 1565 ms 312092 KB Output is correct
33 Correct 1597 ms 310044 KB Output is correct
34 Correct 1538 ms 310620 KB Output is correct
35 Correct 1499 ms 302060 KB Output is correct
36 Correct 1584 ms 312680 KB Output is correct
37 Correct 1595 ms 312032 KB Output is correct
38 Correct 1628 ms 310100 KB Output is correct
39 Execution timed out 2044 ms 709444 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 237136 KB Output is correct
2 Correct 74 ms 237188 KB Output is correct
3 Correct 78 ms 237176 KB Output is correct
4 Correct 77 ms 237048 KB Output is correct
5 Correct 84 ms 237524 KB Output is correct
6 Correct 75 ms 237140 KB Output is correct
7 Correct 80 ms 237232 KB Output is correct
8 Correct 81 ms 237136 KB Output is correct
9 Correct 84 ms 237784 KB Output is correct
10 Correct 84 ms 237652 KB Output is correct
11 Correct 85 ms 237560 KB Output is correct
12 Correct 350 ms 242080 KB Output is correct
13 Correct 371 ms 241764 KB Output is correct
14 Correct 367 ms 242044 KB Output is correct
15 Correct 84 ms 237464 KB Output is correct
16 Correct 85 ms 237396 KB Output is correct
17 Correct 94 ms 237648 KB Output is correct
18 Correct 75 ms 237136 KB Output is correct
19 Correct 135 ms 238112 KB Output is correct
20 Correct 83 ms 237264 KB Output is correct
21 Correct 76 ms 237176 KB Output is correct
22 Correct 110 ms 237576 KB Output is correct
23 Correct 84 ms 237140 KB Output is correct
24 Correct 77 ms 237140 KB Output is correct
25 Correct 79 ms 237140 KB Output is correct
26 Correct 78 ms 237136 KB Output is correct
27 Correct 83 ms 237392 KB Output is correct
28 Correct 96 ms 237652 KB Output is correct
29 Correct 75 ms 237136 KB Output is correct
30 Correct 84 ms 237668 KB Output is correct
31 Correct 84 ms 237656 KB Output is correct
32 Correct 91 ms 237800 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 236972 KB Output is correct
2 Correct 74 ms 237000 KB Output is correct
3 Correct 80 ms 237212 KB Output is correct
4 Correct 75 ms 237012 KB Output is correct
5 Correct 76 ms 237060 KB Output is correct
6 Correct 76 ms 237100 KB Output is correct
7 Correct 93 ms 237648 KB Output is correct
8 Correct 85 ms 237640 KB Output is correct
9 Correct 353 ms 241780 KB Output is correct
10 Correct 361 ms 241744 KB Output is correct
11 Correct 361 ms 242088 KB Output is correct
12 Correct 83 ms 237652 KB Output is correct
13 Correct 74 ms 237140 KB Output is correct
14 Correct 132 ms 238156 KB Output is correct
15 Correct 75 ms 237132 KB Output is correct
16 Correct 108 ms 237648 KB Output is correct
17 Correct 80 ms 237136 KB Output is correct
18 Correct 73 ms 237008 KB Output is correct
19 Correct 73 ms 237008 KB Output is correct
20 Correct 75 ms 237136 KB Output is correct
21 Correct 94 ms 237648 KB Output is correct
22 Correct 83 ms 237652 KB Output is correct
23 Correct 85 ms 237532 KB Output is correct
24 Correct 629 ms 246072 KB Output is correct
25 Correct 1775 ms 272036 KB Output is correct
26 Execution timed out 2072 ms 281432 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 237136 KB Output is correct
2 Correct 74 ms 237188 KB Output is correct
3 Correct 78 ms 237176 KB Output is correct
4 Correct 77 ms 237048 KB Output is correct
5 Correct 84 ms 237524 KB Output is correct
6 Correct 75 ms 237140 KB Output is correct
7 Correct 80 ms 237232 KB Output is correct
8 Correct 81 ms 237136 KB Output is correct
9 Correct 84 ms 237784 KB Output is correct
10 Correct 84 ms 237652 KB Output is correct
11 Correct 85 ms 237560 KB Output is correct
12 Correct 350 ms 242080 KB Output is correct
13 Correct 371 ms 241764 KB Output is correct
14 Correct 367 ms 242044 KB Output is correct
15 Correct 84 ms 237464 KB Output is correct
16 Correct 85 ms 237396 KB Output is correct
17 Correct 94 ms 237648 KB Output is correct
18 Correct 75 ms 237136 KB Output is correct
19 Correct 135 ms 238112 KB Output is correct
20 Correct 83 ms 237264 KB Output is correct
21 Correct 76 ms 237176 KB Output is correct
22 Correct 110 ms 237576 KB Output is correct
23 Correct 84 ms 237140 KB Output is correct
24 Correct 77 ms 237140 KB Output is correct
25 Correct 79 ms 237140 KB Output is correct
26 Correct 78 ms 237136 KB Output is correct
27 Correct 83 ms 237392 KB Output is correct
28 Correct 96 ms 237652 KB Output is correct
29 Correct 75 ms 237136 KB Output is correct
30 Correct 84 ms 237668 KB Output is correct
31 Correct 84 ms 237656 KB Output is correct
32 Correct 91 ms 237800 KB Output is correct
33 Correct 706 ms 266204 KB Output is correct
34 Correct 615 ms 246092 KB Output is correct
35 Correct 160 ms 239444 KB Output is correct
36 Correct 1797 ms 272036 KB Output is correct
37 Correct 527 ms 256880 KB Output is correct
38 Execution timed out 2062 ms 281508 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 237136 KB Output is correct
2 Correct 74 ms 237188 KB Output is correct
3 Correct 78 ms 237176 KB Output is correct
4 Correct 77 ms 237048 KB Output is correct
5 Correct 84 ms 237524 KB Output is correct
6 Correct 75 ms 237140 KB Output is correct
7 Correct 80 ms 237232 KB Output is correct
8 Correct 81 ms 237136 KB Output is correct
9 Correct 84 ms 237784 KB Output is correct
10 Correct 84 ms 237652 KB Output is correct
11 Correct 85 ms 237560 KB Output is correct
12 Correct 350 ms 242080 KB Output is correct
13 Correct 371 ms 241764 KB Output is correct
14 Correct 367 ms 242044 KB Output is correct
15 Correct 84 ms 237464 KB Output is correct
16 Correct 85 ms 237396 KB Output is correct
17 Correct 94 ms 237648 KB Output is correct
18 Correct 75 ms 237136 KB Output is correct
19 Correct 135 ms 238112 KB Output is correct
20 Correct 83 ms 237264 KB Output is correct
21 Correct 76 ms 237176 KB Output is correct
22 Correct 110 ms 237576 KB Output is correct
23 Correct 84 ms 237140 KB Output is correct
24 Correct 77 ms 237140 KB Output is correct
25 Correct 79 ms 237140 KB Output is correct
26 Correct 78 ms 237136 KB Output is correct
27 Correct 83 ms 237392 KB Output is correct
28 Correct 96 ms 237652 KB Output is correct
29 Correct 75 ms 237136 KB Output is correct
30 Correct 84 ms 237668 KB Output is correct
31 Correct 84 ms 237656 KB Output is correct
32 Correct 91 ms 237800 KB Output is correct
33 Correct 706 ms 266204 KB Output is correct
34 Correct 615 ms 246092 KB Output is correct
35 Correct 160 ms 239444 KB Output is correct
36 Correct 1797 ms 272036 KB Output is correct
37 Correct 527 ms 256880 KB Output is correct
38 Execution timed out 2062 ms 281508 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 237192 KB Output is correct
2 Correct 73 ms 237140 KB Output is correct
3 Correct 96 ms 237468 KB Output is correct
4 Correct 85 ms 237656 KB Output is correct
5 Correct 86 ms 237616 KB Output is correct
6 Correct 86 ms 237648 KB Output is correct
7 Correct 85 ms 237652 KB Output is correct
8 Correct 84 ms 237392 KB Output is correct
9 Correct 75 ms 237084 KB Output is correct
10 Correct 98 ms 237144 KB Output is correct
11 Correct 76 ms 236976 KB Output is correct
12 Correct 75 ms 237136 KB Output is correct
13 Correct 76 ms 237136 KB Output is correct
14 Correct 77 ms 237008 KB Output is correct
15 Correct 77 ms 237196 KB Output is correct
16 Correct 85 ms 237568 KB Output is correct
17 Correct 85 ms 237576 KB Output is correct
18 Correct 85 ms 237648 KB Output is correct
19 Correct 666 ms 266424 KB Output is correct
20 Correct 515 ms 256832 KB Output is correct
21 Correct 669 ms 274256 KB Output is correct
22 Correct 679 ms 266836 KB Output is correct
23 Correct 662 ms 266512 KB Output is correct
24 Correct 650 ms 266628 KB Output is correct
25 Correct 647 ms 262920 KB Output is correct
26 Correct 669 ms 267348 KB Output is correct
27 Correct 682 ms 266832 KB Output is correct
28 Correct 664 ms 266548 KB Output is correct
29 Correct 1590 ms 310488 KB Output is correct
30 Correct 667 ms 266712 KB Output is correct
31 Correct 1573 ms 328900 KB Output is correct
32 Correct 1565 ms 312092 KB Output is correct
33 Correct 1597 ms 310044 KB Output is correct
34 Correct 1538 ms 310620 KB Output is correct
35 Correct 1499 ms 302060 KB Output is correct
36 Correct 1584 ms 312680 KB Output is correct
37 Correct 1595 ms 312032 KB Output is correct
38 Correct 1628 ms 310100 KB Output is correct
39 Execution timed out 2044 ms 709444 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 237192 KB Output is correct
2 Correct 73 ms 237140 KB Output is correct
3 Correct 96 ms 237468 KB Output is correct
4 Correct 85 ms 237656 KB Output is correct
5 Correct 86 ms 237616 KB Output is correct
6 Correct 86 ms 237648 KB Output is correct
7 Correct 85 ms 237652 KB Output is correct
8 Correct 84 ms 237392 KB Output is correct
9 Correct 75 ms 237084 KB Output is correct
10 Correct 98 ms 237144 KB Output is correct
11 Correct 76 ms 236976 KB Output is correct
12 Correct 75 ms 237136 KB Output is correct
13 Correct 76 ms 237136 KB Output is correct
14 Correct 77 ms 237008 KB Output is correct
15 Correct 77 ms 237196 KB Output is correct
16 Correct 85 ms 237568 KB Output is correct
17 Correct 85 ms 237576 KB Output is correct
18 Correct 85 ms 237648 KB Output is correct
19 Correct 666 ms 266424 KB Output is correct
20 Correct 515 ms 256832 KB Output is correct
21 Correct 669 ms 274256 KB Output is correct
22 Correct 679 ms 266836 KB Output is correct
23 Correct 662 ms 266512 KB Output is correct
24 Correct 650 ms 266628 KB Output is correct
25 Correct 647 ms 262920 KB Output is correct
26 Correct 669 ms 267348 KB Output is correct
27 Correct 682 ms 266832 KB Output is correct
28 Correct 664 ms 266548 KB Output is correct
29 Correct 1590 ms 310488 KB Output is correct
30 Correct 667 ms 266712 KB Output is correct
31 Correct 1573 ms 328900 KB Output is correct
32 Correct 1565 ms 312092 KB Output is correct
33 Correct 1597 ms 310044 KB Output is correct
34 Correct 1538 ms 310620 KB Output is correct
35 Correct 1499 ms 302060 KB Output is correct
36 Correct 1584 ms 312680 KB Output is correct
37 Correct 1595 ms 312032 KB Output is correct
38 Correct 1628 ms 310100 KB Output is correct
39 Execution timed out 2044 ms 709444 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 237192 KB Output is correct
2 Correct 73 ms 237140 KB Output is correct
3 Correct 96 ms 237468 KB Output is correct
4 Correct 85 ms 237656 KB Output is correct
5 Correct 86 ms 237616 KB Output is correct
6 Correct 86 ms 237648 KB Output is correct
7 Correct 85 ms 237652 KB Output is correct
8 Correct 84 ms 237392 KB Output is correct
9 Correct 75 ms 237084 KB Output is correct
10 Correct 98 ms 237144 KB Output is correct
11 Correct 76 ms 236976 KB Output is correct
12 Correct 75 ms 237136 KB Output is correct
13 Correct 76 ms 237136 KB Output is correct
14 Correct 77 ms 237008 KB Output is correct
15 Correct 77 ms 237196 KB Output is correct
16 Correct 85 ms 237568 KB Output is correct
17 Correct 85 ms 237576 KB Output is correct
18 Correct 85 ms 237648 KB Output is correct
19 Correct 666 ms 266424 KB Output is correct
20 Correct 515 ms 256832 KB Output is correct
21 Correct 669 ms 274256 KB Output is correct
22 Correct 679 ms 266836 KB Output is correct
23 Correct 662 ms 266512 KB Output is correct
24 Correct 650 ms 266628 KB Output is correct
25 Correct 647 ms 262920 KB Output is correct
26 Correct 669 ms 267348 KB Output is correct
27 Correct 682 ms 266832 KB Output is correct
28 Correct 664 ms 266548 KB Output is correct
29 Correct 1590 ms 310488 KB Output is correct
30 Correct 667 ms 266712 KB Output is correct
31 Correct 1573 ms 328900 KB Output is correct
32 Correct 1565 ms 312092 KB Output is correct
33 Correct 1597 ms 310044 KB Output is correct
34 Correct 1538 ms 310620 KB Output is correct
35 Correct 1499 ms 302060 KB Output is correct
36 Correct 1584 ms 312680 KB Output is correct
37 Correct 1595 ms 312032 KB Output is correct
38 Correct 1628 ms 310100 KB Output is correct
39 Execution timed out 2044 ms 709444 KB Time limit exceeded
40 Halted 0 ms 0 KB -