oj.uz

Submission #924401

# Submission time Handle Problem Language Result Execution time Memory
924401 2024-02-09T02:47:13 Z Edu175 Maze (JOI23_ho_t3) C++17
35 / 100
 2000 ms 966764 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto edu:v)cout<<edu<<" "; cout<<"\n"
using namespace std;
typedef int ll;
typedef pair<ll,ll> ii;

#pragma GCC optimize("Ofast") // may lead to precision errors

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll MAXN=6e6+5,R=2500;

ll a[MAXN];
ll n,m,k;
ii mem[MAXN];
vector<vector<ll>>mem2;
//inline ll cv(ii x){return m*x.fst+x.snd;}
//inline ii cv(ll x){return {x/m,x%m};}
inline ll cv(ii x){return mem2[x.fst][x.snd];}
inline ii cv(ll x){return mem[x];}
vector<ll>dir;
//vector<ii>diir={{0,1},{-1,0},{0,-1},{1,0}};
//ii operator+(ii a, ii b){return {a.fst+b.fst,a.snd+b.snd};}
//void operator+=(ii &a, ii b){a=a+b;}
bool allowed(ll x, ll w){
	auto [i,j]=cv(x);
	if(w==0&&j>=m-1)return 0;
	if(w==1&&i<=0)return 0;
	if(w==2&&j<=0)return 0;
	if(w==3&&i>=n-1)return 0;
	return 1;
}
ll d[MAXN],vis[MAXN];
deque<pair<ll,bool>>q;
//set<ll>r[MAXN],c[MAXN];
vector<bitset<MAXN>> r;
vector<bitset<R>> c;

vector<ll>pop;
void go(ll x, ll y, ll g){
	if(vis[y])return;
	d[y]=d[x]+g;
	q.push_front({y,0});
	vis[y]=1;
	pop.pb(y);
}
void popit(){
	for(auto x:pop){
		auto [i,j]=cv(x);
		//r[i].erase(j);
		//c[j].erase(i);
		r[i][j]=c[j][i]=0;
	}
	pop.clear();
}
ll reach(ll _x, ll _e){
	ii x=cv(_x),e=cv(_e);
	return (max(abs(x.fst-e.fst),abs(x.snd-e.snd))<=k&&
	       abs(x.fst-e.fst)+abs(x.snd-e.snd)<2*k);
}

ll bfs(ll s, ll e){
	mset(d,-1);
	d[s]=0;
	q.push_front({s,0});
	while(SZ(q)){
		auto [x,g]=q.front(); q.pop_front();
		if(!g){
			fore(w,0,4){
				auto y=x+dir[w];
				if(!allowed(x,w)||(!g&&a[y]))continue;
				go(x,y,0);
				popit();
			}
			q.pb({x,1});
		}
		else {
			auto [i,j]=cv(x);
			if(reach(x,e)){
				go(x,e,1);
				return d[e];
			}
			if(i-k>=0)
				for(ll it=(j-k<0?0:r[i-k]._Find_next(j-k));it<m&&it<j+k;
				it=r[i-k]._Find_next(it))go(x,cv({i-k,it}),1);
			if(i+k<n)
				for(ll it=(j-k<0?0:r[i+k]._Find_next(j-k));it<m&&it<j+k;
				it=r[i+k]._Find_next(it))go(x,cv({i+k,it}),1);
			if(j-k>=0)
				for(ll it=(i-k<0?0:c[j-k]._Find_next(i-k));it<n&&it<i+k;
				it=c[j-k]._Find_next(it))go(x,cv({it,j-k}),1);
			if(j+k<m)
				for(ll it=(i-k<0?0:c[j+k]._Find_next(i-k));it<n&&it<i+k;
				it=c[j+k]._Find_next(it))go(x,cv({it,j+k}),1);
			popit();
		}
	}
	return d[e];
}

int main(){FIN;
	cin>>n>>m>>k;
	mem2.resize(n,vector<ll>(m));
	r.resize(n),c.resize(m);
	fore(i,0,n)fore(j,0,m){
		mem2[i][j]=m*i+j;
		mem[m*i+j]={i,j};
	}
	dir={1,-m,-1,m};
	ii s,e; cin>>s.fst>>s.snd>>e.fst>>e.snd; s.fst--,s.snd--,e.fst--,e.snd--;
	fore(i,0,n*m){
		char c; cin>>c;
		a[i]=(c=='#');
	}
	fore(i,0,n)fore(j,0,m)r[i][j]=c[j][i]=1;//r[i].insert(j),c[j].insert(i);
	cout<<bfs(cv(s),cv(e))<<"\n";
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 5 ms 27740 KB Output is correct
3 Correct 27 ms 49756 KB Output is correct
4 Correct 28 ms 49752 KB Output is correct
5 Correct 9 ms 49752 KB Output is correct
6 Correct 9 ms 49752 KB Output is correct
7 Correct 4 ms 27992 KB Output is correct
8 Correct 4 ms 28188 KB Output is correct
9 Correct 4 ms 27740 KB Output is correct
10 Correct 4 ms 27740 KB Output is correct
11 Correct 5 ms 29276 KB Output is correct
12 Correct 4 ms 27736 KB Output is correct
13 Correct 4 ms 27736 KB Output is correct
14 Correct 5 ms 28508 KB Output is correct
15 Correct 4 ms 27740 KB Output is correct
16 Correct 12 ms 49756 KB Output is correct
17 Correct 21 ms 49736 KB Output is correct
18 Correct 29 ms 49756 KB Output is correct
19 Correct 304 ms 208752 KB Output is correct
20 Correct 11 ms 42656 KB Output is correct
21 Correct 30 ms 209304 KB Output is correct
22 Correct 104 ms 209012 KB Output is correct
23 Execution timed out 2029 ms 209164 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 28508 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 5 ms 31320 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 27 ms 49880 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 5 ms 30044 KB Output is correct
8 Correct 5 ms 28508 KB Output is correct
9 Correct 28 ms 49752 KB Output is correct
10 Correct 8 ms 49756 KB Output is correct
11 Correct 8 ms 49916 KB Output is correct
12 Correct 7 ms 49860 KB Output is correct
13 Correct 7 ms 49756 KB Output is correct
14 Correct 7 ms 49752 KB Output is correct
15 Correct 4 ms 27996 KB Output is correct
16 Correct 4 ms 27996 KB Output is correct
17 Correct 4 ms 28760 KB Output is correct
18 Correct 4 ms 27740 KB Output is correct
19 Correct 5 ms 34396 KB Output is correct
20 Correct 5 ms 29276 KB Output is correct
21 Correct 4 ms 27736 KB Output is correct
22 Correct 5 ms 35932 KB Output is correct
23 Correct 4 ms 30044 KB Output is correct
24 Correct 5 ms 29276 KB Output is correct
25 Correct 5 ms 27740 KB Output is correct
26 Correct 4 ms 27740 KB Output is correct
27 Correct 5 ms 28508 KB Output is correct
28 Correct 8 ms 38748 KB Output is correct
29 Correct 4 ms 27752 KB Output is correct
30 Correct 12 ms 49756 KB Output is correct
31 Correct 18 ms 49712 KB Output is correct
32 Correct 29 ms 50008 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 28508 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 4 ms 29276 KB Output is correct
6 Correct 6 ms 30044 KB Output is correct
7 Correct 28 ms 49756 KB Output is correct
8 Correct 9 ms 49756 KB Output is correct
9 Correct 6 ms 49756 KB Output is correct
10 Correct 7 ms 49756 KB Output is correct
11 Correct 7 ms 49756 KB Output is correct
12 Correct 4 ms 27992 KB Output is correct
13 Correct 4 ms 27740 KB Output is correct
14 Correct 6 ms 34648 KB Output is correct
15 Correct 4 ms 27740 KB Output is correct
16 Correct 5 ms 35972 KB Output is correct
17 Correct 4 ms 30044 KB Output is correct
18 Correct 5 ms 29276 KB Output is correct
19 Correct 4 ms 27740 KB Output is correct
20 Correct 4 ms 27740 KB Output is correct
21 Correct 6 ms 38748 KB Output is correct
22 Correct 11 ms 49728 KB Output is correct
23 Correct 19 ms 49756 KB Output is correct
24 Correct 7 ms 52828 KB Output is correct
25 Correct 11 ms 73820 KB Output is correct
26 Correct 12 ms 63324 KB Output is correct
27 Correct 30 ms 209244 KB Output is correct
28 Correct 28 ms 209232 KB Output is correct
29 Correct 26 ms 208720 KB Output is correct
30 Correct 26 ms 208464 KB Output is correct
31 Correct 12 ms 75356 KB Output is correct
32 Correct 103 ms 209012 KB Output is correct
33 Correct 36 ms 208652 KB Output is correct
34 Correct 30 ms 179280 KB Output is correct
35 Correct 84 ms 313636 KB Output is correct
36 Correct 67 ms 313684 KB Output is correct
37 Correct 59 ms 311692 KB Output is correct
38 Correct 60 ms 311736 KB Output is correct
39 Correct 140 ms 477660 KB Output is correct
40 Correct 102 ms 141264 KB Output is correct
41 Correct 520 ms 965776 KB Output is correct
42 Correct 498 ms 966764 KB Output is correct
43 Correct 302 ms 948496 KB Output is correct
44 Correct 302 ms 948564 KB Output is correct
45 Correct 139 ms 125096 KB Output is correct
46 Correct 135 ms 153656 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 28508 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 5 ms 31320 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 27 ms 49880 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 5 ms 30044 KB Output is correct
8 Correct 5 ms 28508 KB Output is correct
9 Correct 28 ms 49752 KB Output is correct
10 Correct 8 ms 49756 KB Output is correct
11 Correct 8 ms 49916 KB Output is correct
12 Correct 7 ms 49860 KB Output is correct
13 Correct 7 ms 49756 KB Output is correct
14 Correct 7 ms 49752 KB Output is correct
15 Correct 4 ms 27996 KB Output is correct
16 Correct 4 ms 27996 KB Output is correct
17 Correct 4 ms 28760 KB Output is correct
18 Correct 4 ms 27740 KB Output is correct
19 Correct 5 ms 34396 KB Output is correct
20 Correct 5 ms 29276 KB Output is correct
21 Correct 4 ms 27736 KB Output is correct
22 Correct 5 ms 35932 KB Output is correct
23 Correct 4 ms 30044 KB Output is correct
24 Correct 5 ms 29276 KB Output is correct
25 Correct 5 ms 27740 KB Output is correct
26 Correct 4 ms 27740 KB Output is correct
27 Correct 5 ms 28508 KB Output is correct
28 Correct 8 ms 38748 KB Output is correct
29 Correct 4 ms 27752 KB Output is correct
30 Correct 12 ms 49756 KB Output is correct
31 Correct 18 ms 49712 KB Output is correct
32 Correct 29 ms 50008 KB Output is correct
33 Correct 284 ms 208980 KB Output is correct
34 Correct 7 ms 52828 KB Output is correct
35 Correct 5 ms 29276 KB Output is correct
36 Correct 10 ms 73820 KB Output is correct
37 Correct 11 ms 42660 KB Output is correct
38 Correct 12 ms 63324 KB Output is correct
39 Correct 30 ms 209176 KB Output is correct
40 Correct 95 ms 208792 KB Output is correct
41 Execution timed out 2067 ms 209180 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 28508 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 5 ms 31320 KB Output is correct
4 Correct 4 ms 27740 KB Output is correct
5 Correct 27 ms 49880 KB Output is correct
6 Correct 4 ms 29276 KB Output is correct
7 Correct 5 ms 30044 KB Output is correct
8 Correct 5 ms 28508 KB Output is correct
9 Correct 28 ms 49752 KB Output is correct
10 Correct 8 ms 49756 KB Output is correct
11 Correct 8 ms 49916 KB Output is correct
12 Correct 7 ms 49860 KB Output is correct
13 Correct 7 ms 49756 KB Output is correct
14 Correct 7 ms 49752 KB Output is correct
15 Correct 4 ms 27996 KB Output is correct
16 Correct 4 ms 27996 KB Output is correct
17 Correct 4 ms 28760 KB Output is correct
18 Correct 4 ms 27740 KB Output is correct
19 Correct 5 ms 34396 KB Output is correct
20 Correct 5 ms 29276 KB Output is correct
21 Correct 4 ms 27736 KB Output is correct
22 Correct 5 ms 35932 KB Output is correct
23 Correct 4 ms 30044 KB Output is correct
24 Correct 5 ms 29276 KB Output is correct
25 Correct 5 ms 27740 KB Output is correct
26 Correct 4 ms 27740 KB Output is correct
27 Correct 5 ms 28508 KB Output is correct
28 Correct 8 ms 38748 KB Output is correct
29 Correct 4 ms 27752 KB Output is correct
30 Correct 12 ms 49756 KB Output is correct
31 Correct 18 ms 49712 KB Output is correct
32 Correct 29 ms 50008 KB Output is correct
33 Correct 284 ms 208980 KB Output is correct
34 Correct 7 ms 52828 KB Output is correct
35 Correct 5 ms 29276 KB Output is correct
36 Correct 10 ms 73820 KB Output is correct
37 Correct 11 ms 42660 KB Output is correct
38 Correct 12 ms 63324 KB Output is correct
39 Correct 30 ms 209176 KB Output is correct
40 Correct 95 ms 208792 KB Output is correct
41 Execution timed out 2067 ms 209180 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 5 ms 27740 KB Output is correct
3 Correct 27 ms 49756 KB Output is correct
4 Correct 28 ms 49752 KB Output is correct
5 Correct 9 ms 49752 KB Output is correct
6 Correct 9 ms 49752 KB Output is correct
7 Correct 4 ms 27992 KB Output is correct
8 Correct 4 ms 28188 KB Output is correct
9 Correct 4 ms 27740 KB Output is correct
10 Correct 4 ms 27740 KB Output is correct
11 Correct 5 ms 29276 KB Output is correct
12 Correct 4 ms 27736 KB Output is correct
13 Correct 4 ms 27736 KB Output is correct
14 Correct 5 ms 28508 KB Output is correct
15 Correct 4 ms 27740 KB Output is correct
16 Correct 12 ms 49756 KB Output is correct
17 Correct 21 ms 49736 KB Output is correct
18 Correct 29 ms 49756 KB Output is correct
19 Correct 304 ms 208752 KB Output is correct
20 Correct 11 ms 42656 KB Output is correct
21 Correct 30 ms 209304 KB Output is correct
22 Correct 104 ms 209012 KB Output is correct
23 Execution timed out 2029 ms 209164 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 5 ms 27740 KB Output is correct
3 Correct 27 ms 49756 KB Output is correct
4 Correct 28 ms 49752 KB Output is correct
5 Correct 9 ms 49752 KB Output is correct
6 Correct 9 ms 49752 KB Output is correct
7 Correct 4 ms 27992 KB Output is correct
8 Correct 4 ms 28188 KB Output is correct
9 Correct 4 ms 27740 KB Output is correct
10 Correct 4 ms 27740 KB Output is correct
11 Correct 5 ms 29276 KB Output is correct
12 Correct 4 ms 27736 KB Output is correct
13 Correct 4 ms 27736 KB Output is correct
14 Correct 5 ms 28508 KB Output is correct
15 Correct 4 ms 27740 KB Output is correct
16 Correct 12 ms 49756 KB Output is correct
17 Correct 21 ms 49736 KB Output is correct
18 Correct 29 ms 49756 KB Output is correct
19 Correct 304 ms 208752 KB Output is correct
20 Correct 11 ms 42656 KB Output is correct
21 Correct 30 ms 209304 KB Output is correct
22 Correct 104 ms 209012 KB Output is correct
23 Execution timed out 2029 ms 209164 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 5 ms 27740 KB Output is correct
3 Correct 27 ms 49756 KB Output is correct
4 Correct 28 ms 49752 KB Output is correct
5 Correct 9 ms 49752 KB Output is correct
6 Correct 9 ms 49752 KB Output is correct
7 Correct 4 ms 27992 KB Output is correct
8 Correct 4 ms 28188 KB Output is correct
9 Correct 4 ms 27740 KB Output is correct
10 Correct 4 ms 27740 KB Output is correct
11 Correct 5 ms 29276 KB Output is correct
12 Correct 4 ms 27736 KB Output is correct
13 Correct 4 ms 27736 KB Output is correct
14 Correct 5 ms 28508 KB Output is correct
15 Correct 4 ms 27740 KB Output is correct
16 Correct 12 ms 49756 KB Output is correct
17 Correct 21 ms 49736 KB Output is correct
18 Correct 29 ms 49756 KB Output is correct
19 Correct 304 ms 208752 KB Output is correct
20 Correct 11 ms 42656 KB Output is correct
21 Correct 30 ms 209304 KB Output is correct
22 Correct 104 ms 209012 KB Output is correct
23 Execution timed out 2029 ms 209164 KB Time limit exceeded
24 Halted 0 ms 0 KB -