Submission #197354

#	Time	Username	Problem	Language	Result	Execution time	Memory
197354		dndhk	Portals (BOI14_portals)	C++14	20 / 100	49 ms	33272 KiB

portals

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 1000000;
const ll INFLL = 1e18;
const int MAX_N = 1000;

int N, M;
string str[MAX_N+1];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int d1[MAX_N+1][MAX_N+1];
pii nxt[4][MAX_N+1][MAX_N+1];
int dist[MAX_N+1][MAX_N+1];
deque<pii> dq;
pii s, e;

vector<pair<pii, int> > gp[MAX_N+1][MAX_N+1];
bool vst[MAX_N+1][MAX_N+1];
priority_queue<pair<int, pii>  , vector<pair<int, pii> > , greater<pair<int, pii> > > pq;

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<N; i++){
		cin>>str[i];
		for(int j=0; j<M; j++){
			if(str[i][j]=='S'){
				s = {i, j};
				str[i][j] = '.';
			}
			if(str[i][j]=='C'){
				e = {i, j};
				str[i][j] = '.';
			}
			if(str[i][j]=='.'){
				d1[i][j] = INF;
				if(i==0 || i==N-1 || j==0 || j==M-1){
					d1[i][j] = 0;
					dq.pb({i, j});
				}else{
					for(int k=0; k<4; k++){
						if(str[i+dx[k]][j+dy[k]]=='#'){
							d1[i][j] = 0;
							dq.pb({i, j});
							break;
						}
					}
				}
			}
		}
	}
	while(!dq.empty()){
		pii now = dq.front(); dq.pop_front();
		for(int i=0; i<4; i++){
			if(now.first+dx[i]<0 || now.first+dx[i]>=N || now.second+dy[i]<0 || now.second+dy[i]>=M)	continue;
			if(str[now.first+dx[i]][now.second+dy[i]]=='#')	continue;
			if(d1[now.first+dx[i]][now.second+dy[i]]>d1[now.first][now.second]+1){
				d1[now.first+dx[i]][now.second+dy[i]] = d1[now.first][now.second] + 1;
				dq.pb({now.first+dx[i], now.second+dy[i]});
			}
		}
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(str[i][j]=='.'){
				if(i==0 || str[i-1][j]=='#'){
					int l = i, r = i;
					while(r<N-1 && str[r+1][j]=='.'){
						r++;
					}
					for(int k=l; k<=r; k++){
						nxt[0][k][j] = {l, j};
						nxt[1][k][j] = {r, j};
					}
				}
				if(j==0 || str[i][j-1]=='#'){
					int l = j, r = j;
					while(r<M-1 && str[i][r+1]=='.'){
						r++;
					}
					for(int k=l; k<=r; k++){
						nxt[2][i][k] = {i, l};
						nxt[3][i][k] = {i, r};
					}
				}
			}
		}
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(str[i][j]=='.'){
				for(int k=0; k<4; k++){
					gp[i][j].pb({nxt[k][i][j], 1});
					if(i+dx[k]<0 || i+dx[k]>=N || j+dy[k]<0 || j+dy[k]>=M)	continue;
					if(str[i+dx[k]][j+dy[k]]=='#')	continue;
					gp[i][j].pb({{i+dx[k], j+dy[k]}, 1});
				}
				dist[i][j] = INF;
			}
		}
	}
	dist[s.first][s.second] = 0;
	pq.push({0, s});
	while(!pq.empty()){
		pii p = pq.top().second; pq.pop();
		if(vst[p.first][p.second])	continue;
		//cout<<p.first<<" "<<p.second<<" "<<dist[p.first][p.second]<<endl;
		vst[p.first][p.second] = true;
		for(pair<pii, int>  i : gp[p.first][p.second]){
			if(dist[i.first.first][i.first.second]>dist[p.first][p.second] + i.second){
				dist[i.first.first][i.first.second] = dist[p.first][p.second] + i.second;
				pq.push({dist[i.first.first][i.first.second], i.first});
			}
		}
	}
	cout<<dist[e.first][e.second];
	return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30