oj.uz

Submission #553440

# Submission time Handle Problem Language Result Execution time Memory
553440 2022-04-25T20:32:37 Z new_acc Portals (BOI14_portals) C++14
0 / 100
 13 ms 3008 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e3+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int last[N][N][4],odl[N][N],m,n;
char t[N][N];
set<pair<int,pair<int,int> > >deq;
bool vis[N][N];
bool inn(int a,int b){
	return (a>=1 and a<=n and b>=1 and b<=m and t[a][b]!='#');
}
void add(int a,int b){
	if(vis[a][b]) return;
	vis[a][b]=1;
	if(inn(a-1,b) and !vis[a-1][b]) deq.insert({odl[a][b]+1,{a-1,b}});
	if(inn(a+1,b) and !vis[a+1][b]) deq.insert({odl[a][b]+1,{a+1,b}});
	if(inn(a,b+1) and !vis[a][b+1]) deq.insert({odl[a][b]+1,{a,b+1}});
	if(inn(a,b-1) and !vis[a][b-1]) deq.insert({odl[a][b]+1,{a,b-1}});
	int naj=min({b-last[a][b][0],last[a][b][1]-b,a-last[a][b][2],last[a][b][3]-a});
	if(!vis[a][last[a][b][0]]) deq.insert({odl[a][b]+naj+1,{a,last[a][b][0]}});
	if(!vis[a][last[a][b][1]]) deq.insert({odl[a][b]+naj+1,{a,last[a][b][1]}});
	if(!vis[last[a][b][2]][b]) deq.insert({odl[a][b]+naj+1,{last[a][b][2],b}});
	if(!vis[last[a][b][3]][b]) deq.insert({odl[a][b]+naj+1,{last[a][b][3],b}});
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) cin>>t[i][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(t[i][j-1]=='#' or j==1) last[i][j][0]=j;
			else last[i][j][0]=last[i][j-1][0];
		}	
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			if(t[i][j+1]=='#' or j==m) last[i][j][1]=j;
			else last[i][j][1]=last[i][j+1][1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(t[i-1][j]=='#' or i==1) last[i][j][2]=i;
			else last[i][j][2]=last[i-1][j][2];
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=1;j<=m;j++){
			if(t[i+1][j]=='#' or i==n) last[i][j][3]=i;
			else last[i][j][3]=last[i+1][j][3];
		}
	}
	pair<int,int>s,tt;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
		 	if(t[i][j]=='S') s={i,j};
		 	if(t[i][j]=='C') tt={i,j};
		}
	}
	deq.insert({0,s});
	while(deq.size()){
		auto it=deq.begin();
		pair<int,pair<int,int> >v=*it;
		deq.erase(it);
		odl[v.se.fi][v.se.se]=v.fi;
		add(v.se.fi,v.se.se);
	}
	cout<<odl[tt.fi][tt.se]<<"\n";
}
int main(){
	solve();
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 1 ms 312 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 316 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 10 ms 3008 KB Output is correct
6 Correct 11 ms 2900 KB Output is correct
7 Correct 13 ms 2928 KB Output is correct
8 Incorrect 5 ms 2900 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 316 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -