oj.uz

Submission #936591

# Submission time Handle Problem Language Result Execution time Memory
936591 2024-03-02T09:27:56 Z penguin133 Maze (JOI23_ho_t3) C++17
19 / 100
 2000 ms 1730536 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);
				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 93 ms 237168 KB Output is correct
2 Correct 75 ms 237136 KB Output is correct
3 Correct 74 ms 237580 KB Output is correct
4 Correct 75 ms 237768 KB Output is correct
5 Correct 75 ms 237488 KB Output is correct
6 Correct 73 ms 237392 KB Output is correct
7 Correct 74 ms 237528 KB Output is correct
8 Correct 86 ms 237400 KB Output is correct
9 Correct 74 ms 237120 KB Output is correct
10 Correct 74 ms 237136 KB Output is correct
11 Correct 73 ms 237188 KB Output is correct
12 Correct 77 ms 237176 KB Output is correct
13 Correct 74 ms 237140 KB Output is correct
14 Correct 75 ms 237136 KB Output is correct
15 Correct 73 ms 237200 KB Output is correct
16 Correct 76 ms 237652 KB Output is correct
17 Correct 80 ms 237652 KB Output is correct
18 Correct 76 ms 237464 KB Output is correct
19 Correct 137 ms 265476 KB Output is correct
20 Correct 123 ms 255820 KB Output is correct
21 Correct 153 ms 273488 KB Output is correct
22 Correct 145 ms 266044 KB Output is correct
23 Correct 141 ms 265636 KB Output is correct
24 Correct 123 ms 265300 KB Output is correct
25 Correct 118 ms 261876 KB Output is correct
26 Correct 152 ms 266404 KB Output is correct
27 Correct 143 ms 266084 KB Output is correct
28 Correct 145 ms 265436 KB Output is correct
29 Correct 233 ms 307996 KB Output is correct
30 Correct 135 ms 265440 KB Output is correct
31 Correct 277 ms 326680 KB Output is correct
32 Correct 249 ms 309484 KB Output is correct
33 Correct 244 ms 307444 KB Output is correct
34 Correct 203 ms 307808 KB Output is correct
35 Correct 185 ms 298836 KB Output is correct
36 Correct 266 ms 310352 KB Output is correct
37 Correct 264 ms 309564 KB Output is correct
38 Correct 259 ms 307620 KB Output is correct
39 Correct 1783 ms 932492 KB Output is correct
40 Correct 283 ms 320368 KB Output is correct
41 Correct 221 ms 320568 KB Output is correct
42 Correct 304 ms 338296 KB Output is correct
43 Correct 315 ms 347656 KB Output is correct
44 Correct 996 ms 608004 KB Output is correct
45 Correct 916 ms 605452 KB Output is correct
46 Execution timed out 2084 ms 1106384 KB Time limit exceeded
47 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 237140 KB Output is correct
2 Correct 75 ms 237192 KB Output is correct
3 Correct 75 ms 237212 KB Output is correct
4 Correct 74 ms 237136 KB Output is correct
5 Correct 76 ms 237468 KB Output is correct
6 Correct 74 ms 236960 KB Output is correct
7 Correct 81 ms 237136 KB Output is correct
8 Correct 75 ms 237220 KB Output is correct
9 Correct 79 ms 237780 KB Output is correct
10 Correct 74 ms 237556 KB Output is correct
11 Correct 75 ms 237396 KB Output is correct
12 Correct 90 ms 241316 KB Output is correct
13 Correct 81 ms 241492 KB Output is correct
14 Correct 82 ms 241488 KB Output is correct
15 Correct 74 ms 237592 KB Output is correct
16 Correct 73 ms 237592 KB Output is correct
17 Correct 82 ms 237676 KB Output is correct
18 Correct 73 ms 237392 KB Output is correct
19 Correct 74 ms 238020 KB Output is correct
20 Correct 76 ms 237180 KB Output is correct
21 Correct 86 ms 237108 KB Output is correct
22 Correct 77 ms 237688 KB Output is correct
23 Correct 111 ms 237220 KB Output is correct
24 Correct 119 ms 236972 KB Output is correct
25 Correct 111 ms 236980 KB Output is correct
26 Correct 118 ms 237124 KB Output is correct
27 Correct 110 ms 237244 KB Output is correct
28 Correct 112 ms 237396 KB Output is correct
29 Correct 110 ms 237140 KB Output is correct
30 Correct 115 ms 237608 KB Output is correct
31 Correct 112 ms 237652 KB Output is correct
32 Correct 112 ms 237636 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 237180 KB Output is correct
2 Correct 114 ms 237140 KB Output is correct
3 Correct 107 ms 237116 KB Output is correct
4 Correct 109 ms 236984 KB Output is correct
5 Correct 122 ms 237136 KB Output is correct
6 Correct 111 ms 237140 KB Output is correct
7 Correct 111 ms 237724 KB Output is correct
8 Correct 109 ms 237420 KB Output is correct
9 Correct 111 ms 241316 KB Output is correct
10 Correct 133 ms 241748 KB Output is correct
11 Correct 115 ms 241492 KB Output is correct
12 Correct 78 ms 237504 KB Output is correct
13 Correct 74 ms 236964 KB Output is correct
14 Correct 84 ms 238120 KB Output is correct
15 Correct 74 ms 237136 KB Output is correct
16 Correct 82 ms 237496 KB Output is correct
17 Correct 74 ms 237156 KB Output is correct
18 Correct 74 ms 237196 KB Output is correct
19 Correct 74 ms 237168 KB Output is correct
20 Correct 73 ms 237136 KB Output is correct
21 Correct 73 ms 237396 KB Output is correct
22 Correct 75 ms 237556 KB Output is correct
23 Correct 76 ms 237652 KB Output is correct
24 Correct 87 ms 245328 KB Output is correct
25 Correct 147 ms 269048 KB Output is correct
26 Correct 220 ms 307796 KB Output is correct
27 Correct 149 ms 273236 KB Output is correct
28 Execution timed out 2136 ms 1730536 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 237140 KB Output is correct
2 Correct 75 ms 237192 KB Output is correct
3 Correct 75 ms 237212 KB Output is correct
4 Correct 74 ms 237136 KB Output is correct
5 Correct 76 ms 237468 KB Output is correct
6 Correct 74 ms 236960 KB Output is correct
7 Correct 81 ms 237136 KB Output is correct
8 Correct 75 ms 237220 KB Output is correct
9 Correct 79 ms 237780 KB Output is correct
10 Correct 74 ms 237556 KB Output is correct
11 Correct 75 ms 237396 KB Output is correct
12 Correct 90 ms 241316 KB Output is correct
13 Correct 81 ms 241492 KB Output is correct
14 Correct 82 ms 241488 KB Output is correct
15 Correct 74 ms 237592 KB Output is correct
16 Correct 73 ms 237592 KB Output is correct
17 Correct 82 ms 237676 KB Output is correct
18 Correct 73 ms 237392 KB Output is correct
19 Correct 74 ms 238020 KB Output is correct
20 Correct 76 ms 237180 KB Output is correct
21 Correct 86 ms 237108 KB Output is correct
22 Correct 77 ms 237688 KB Output is correct
23 Correct 111 ms 237220 KB Output is correct
24 Correct 119 ms 236972 KB Output is correct
25 Correct 111 ms 236980 KB Output is correct
26 Correct 118 ms 237124 KB Output is correct
27 Correct 110 ms 237244 KB Output is correct
28 Correct 112 ms 237396 KB Output is correct
29 Correct 110 ms 237140 KB Output is correct
30 Correct 115 ms 237608 KB Output is correct
31 Correct 112 ms 237652 KB Output is correct
32 Correct 112 ms 237636 KB Output is correct
33 Correct 137 ms 265368 KB Output is correct
34 Correct 82 ms 245300 KB Output is correct
35 Correct 75 ms 239440 KB Output is correct
36 Correct 142 ms 269112 KB Output is correct
37 Correct 104 ms 255908 KB Output is correct
38 Correct 222 ms 307948 KB Output is correct
39 Correct 137 ms 277332 KB Output is correct
40 Correct 127 ms 269872 KB Output is correct
41 Correct 123 ms 269384 KB Output is correct
42 Execution timed out 2095 ms 1683232 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 237140 KB Output is correct
2 Correct 75 ms 237192 KB Output is correct
3 Correct 75 ms 237212 KB Output is correct
4 Correct 74 ms 237136 KB Output is correct
5 Correct 76 ms 237468 KB Output is correct
6 Correct 74 ms 236960 KB Output is correct
7 Correct 81 ms 237136 KB Output is correct
8 Correct 75 ms 237220 KB Output is correct
9 Correct 79 ms 237780 KB Output is correct
10 Correct 74 ms 237556 KB Output is correct
11 Correct 75 ms 237396 KB Output is correct
12 Correct 90 ms 241316 KB Output is correct
13 Correct 81 ms 241492 KB Output is correct
14 Correct 82 ms 241488 KB Output is correct
15 Correct 74 ms 237592 KB Output is correct
16 Correct 73 ms 237592 KB Output is correct
17 Correct 82 ms 237676 KB Output is correct
18 Correct 73 ms 237392 KB Output is correct
19 Correct 74 ms 238020 KB Output is correct
20 Correct 76 ms 237180 KB Output is correct
21 Correct 86 ms 237108 KB Output is correct
22 Correct 77 ms 237688 KB Output is correct
23 Correct 111 ms 237220 KB Output is correct
24 Correct 119 ms 236972 KB Output is correct
25 Correct 111 ms 236980 KB Output is correct
26 Correct 118 ms 237124 KB Output is correct
27 Correct 110 ms 237244 KB Output is correct
28 Correct 112 ms 237396 KB Output is correct
29 Correct 110 ms 237140 KB Output is correct
30 Correct 115 ms 237608 KB Output is correct
31 Correct 112 ms 237652 KB Output is correct
32 Correct 112 ms 237636 KB Output is correct
33 Correct 137 ms 265368 KB Output is correct
34 Correct 82 ms 245300 KB Output is correct
35 Correct 75 ms 239440 KB Output is correct
36 Correct 142 ms 269112 KB Output is correct
37 Correct 104 ms 255908 KB Output is correct
38 Correct 222 ms 307948 KB Output is correct
39 Correct 137 ms 277332 KB Output is correct
40 Correct 127 ms 269872 KB Output is correct
41 Correct 123 ms 269384 KB Output is correct
42 Execution timed out 2095 ms 1683232 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 237168 KB Output is correct
2 Correct 75 ms 237136 KB Output is correct
3 Correct 74 ms 237580 KB Output is correct
4 Correct 75 ms 237768 KB Output is correct
5 Correct 75 ms 237488 KB Output is correct
6 Correct 73 ms 237392 KB Output is correct
7 Correct 74 ms 237528 KB Output is correct
8 Correct 86 ms 237400 KB Output is correct
9 Correct 74 ms 237120 KB Output is correct
10 Correct 74 ms 237136 KB Output is correct
11 Correct 73 ms 237188 KB Output is correct
12 Correct 77 ms 237176 KB Output is correct
13 Correct 74 ms 237140 KB Output is correct
14 Correct 75 ms 237136 KB Output is correct
15 Correct 73 ms 237200 KB Output is correct
16 Correct 76 ms 237652 KB Output is correct
17 Correct 80 ms 237652 KB Output is correct
18 Correct 76 ms 237464 KB Output is correct
19 Correct 137 ms 265476 KB Output is correct
20 Correct 123 ms 255820 KB Output is correct
21 Correct 153 ms 273488 KB Output is correct
22 Correct 145 ms 266044 KB Output is correct
23 Correct 141 ms 265636 KB Output is correct
24 Correct 123 ms 265300 KB Output is correct
25 Correct 118 ms 261876 KB Output is correct
26 Correct 152 ms 266404 KB Output is correct
27 Correct 143 ms 266084 KB Output is correct
28 Correct 145 ms 265436 KB Output is correct
29 Correct 233 ms 307996 KB Output is correct
30 Correct 135 ms 265440 KB Output is correct
31 Correct 277 ms 326680 KB Output is correct
32 Correct 249 ms 309484 KB Output is correct
33 Correct 244 ms 307444 KB Output is correct
34 Correct 203 ms 307808 KB Output is correct
35 Correct 185 ms 298836 KB Output is correct
36 Correct 266 ms 310352 KB Output is correct
37 Correct 264 ms 309564 KB Output is correct
38 Correct 259 ms 307620 KB Output is correct
39 Correct 1783 ms 932492 KB Output is correct
40 Correct 283 ms 320368 KB Output is correct
41 Correct 221 ms 320568 KB Output is correct
42 Correct 304 ms 338296 KB Output is correct
43 Correct 315 ms 347656 KB Output is correct
44 Correct 996 ms 608004 KB Output is correct
45 Correct 916 ms 605452 KB Output is correct
46 Execution timed out 2084 ms 1106384 KB Time limit exceeded
47 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 237168 KB Output is correct
2 Correct 75 ms 237136 KB Output is correct
3 Correct 74 ms 237580 KB Output is correct
4 Correct 75 ms 237768 KB Output is correct
5 Correct 75 ms 237488 KB Output is correct
6 Correct 73 ms 237392 KB Output is correct
7 Correct 74 ms 237528 KB Output is correct
8 Correct 86 ms 237400 KB Output is correct
9 Correct 74 ms 237120 KB Output is correct
10 Correct 74 ms 237136 KB Output is correct
11 Correct 73 ms 237188 KB Output is correct
12 Correct 77 ms 237176 KB Output is correct
13 Correct 74 ms 237140 KB Output is correct
14 Correct 75 ms 237136 KB Output is correct
15 Correct 73 ms 237200 KB Output is correct
16 Correct 76 ms 237652 KB Output is correct
17 Correct 80 ms 237652 KB Output is correct
18 Correct 76 ms 237464 KB Output is correct
19 Correct 137 ms 265476 KB Output is correct
20 Correct 123 ms 255820 KB Output is correct
21 Correct 153 ms 273488 KB Output is correct
22 Correct 145 ms 266044 KB Output is correct
23 Correct 141 ms 265636 KB Output is correct
24 Correct 123 ms 265300 KB Output is correct
25 Correct 118 ms 261876 KB Output is correct
26 Correct 152 ms 266404 KB Output is correct
27 Correct 143 ms 266084 KB Output is correct
28 Correct 145 ms 265436 KB Output is correct
29 Correct 233 ms 307996 KB Output is correct
30 Correct 135 ms 265440 KB Output is correct
31 Correct 277 ms 326680 KB Output is correct
32 Correct 249 ms 309484 KB Output is correct
33 Correct 244 ms 307444 KB Output is correct
34 Correct 203 ms 307808 KB Output is correct
35 Correct 185 ms 298836 KB Output is correct
36 Correct 266 ms 310352 KB Output is correct
37 Correct 264 ms 309564 KB Output is correct
38 Correct 259 ms 307620 KB Output is correct
39 Correct 1783 ms 932492 KB Output is correct
40 Correct 283 ms 320368 KB Output is correct
41 Correct 221 ms 320568 KB Output is correct
42 Correct 304 ms 338296 KB Output is correct
43 Correct 315 ms 347656 KB Output is correct
44 Correct 996 ms 608004 KB Output is correct
45 Correct 916 ms 605452 KB Output is correct
46 Execution timed out 2084 ms 1106384 KB Time limit exceeded
47 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 237168 KB Output is correct
2 Correct 75 ms 237136 KB Output is correct
3 Correct 74 ms 237580 KB Output is correct
4 Correct 75 ms 237768 KB Output is correct
5 Correct 75 ms 237488 KB Output is correct
6 Correct 73 ms 237392 KB Output is correct
7 Correct 74 ms 237528 KB Output is correct
8 Correct 86 ms 237400 KB Output is correct
9 Correct 74 ms 237120 KB Output is correct
10 Correct 74 ms 237136 KB Output is correct
11 Correct 73 ms 237188 KB Output is correct
12 Correct 77 ms 237176 KB Output is correct
13 Correct 74 ms 237140 KB Output is correct
14 Correct 75 ms 237136 KB Output is correct
15 Correct 73 ms 237200 KB Output is correct
16 Correct 76 ms 237652 KB Output is correct
17 Correct 80 ms 237652 KB Output is correct
18 Correct 76 ms 237464 KB Output is correct
19 Correct 137 ms 265476 KB Output is correct
20 Correct 123 ms 255820 KB Output is correct
21 Correct 153 ms 273488 KB Output is correct
22 Correct 145 ms 266044 KB Output is correct
23 Correct 141 ms 265636 KB Output is correct
24 Correct 123 ms 265300 KB Output is correct
25 Correct 118 ms 261876 KB Output is correct
26 Correct 152 ms 266404 KB Output is correct
27 Correct 143 ms 266084 KB Output is correct
28 Correct 145 ms 265436 KB Output is correct
29 Correct 233 ms 307996 KB Output is correct
30 Correct 135 ms 265440 KB Output is correct
31 Correct 277 ms 326680 KB Output is correct
32 Correct 249 ms 309484 KB Output is correct
33 Correct 244 ms 307444 KB Output is correct
34 Correct 203 ms 307808 KB Output is correct
35 Correct 185 ms 298836 KB Output is correct
36 Correct 266 ms 310352 KB Output is correct
37 Correct 264 ms 309564 KB Output is correct
38 Correct 259 ms 307620 KB Output is correct
39 Correct 1783 ms 932492 KB Output is correct
40 Correct 283 ms 320368 KB Output is correct
41 Correct 221 ms 320568 KB Output is correct
42 Correct 304 ms 338296 KB Output is correct
43 Correct 315 ms 347656 KB Output is correct
44 Correct 996 ms 608004 KB Output is correct
45 Correct 916 ms 605452 KB Output is correct
46 Execution timed out 2084 ms 1106384 KB Time limit exceeded
47 Halted 0 ms 0 KB -