Submission #58861

#	Time	Username	Problem	Language	Result	Execution time	Memory
58861		Mamnoon_Siam	Portals (BOI14_portals)	C++17	70 / 100	517 ms	242096 KiB

portals

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<
	T,
	null_type,
	less<T>, // use less_equal to use as multiset without erase operation
	rb_tree_tag,
	tree_order_statistics_node_update>;
 
// gives the number of keys with value strictly less than x
#define lesscount(x) order_of_key(x)
// gives the iterator to kth element (starting from 0)
#define kthiterator(x) find_by_order(x)
 
#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define readfile(s) freopen(s, "r", stdin)
#define writefile(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(g) g.begin(), g.end()
#define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL)
#define printBinary(n) cout << #n << " = " << bitset<64>(n) << endl
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define cin(n) scanf("%d", &n)
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
 
inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }
 
typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;
 
template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_, T d_) { return min(min(a_, b_),min(c_,d_)); }
template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(c_,d_)); }
//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};
 
template<typename T> inline T ceil(T num, T d)
{ return (T)(num/d) + (num%d>(T)0 ? (T)1 : (T)0); }
#define block_no(idx) 		(idx/BLOCK_SIZE)
#define block_starting(idx) (block_no(idx)*BLOCK_SIZE)
#define block_ending(idx) 	(min(n, block_no(idx)*BLOCK_SIZE+BLOCK_SIZE-1))
#define block_rank(idx) 	(idx%BLOCK_SIZE)

#define left skldjfl
#define right dkfljgdlfk
 
const int maxn = 1005;
 
#define lg 10
#define node(x, y) (((x)<<(lg))|(y))
 
vector<pair<int, int> > g[node(maxn, maxn)+10];
int e[maxn*maxn], vis[maxn*maxn], n, m;
char s[maxn][maxn];
int link[maxn*maxn];
int up[maxn][maxn], down[maxn][maxn], left[maxn][maxn], right[maxn][maxn];
vector<int> pq[maxn * maxn];

int Up(int i, int j) {
	if(s[i][j] == '#') return i + 1;
	int &ret = up[i][j];
	if(ret != -1) return ret;
	return ret = Up(i - 1, j);
}
int Down(int i, int j) {
	if(s[i][j] == '#') return i - 1;
	int &ret = down[i][j];
	if(ret != -1) return ret;
	return ret = Down(i + 1, j);
}
int Left(int i, int j) {
	if(s[i][j] == '#') return j + 1;
	int &ret = left[i][j];
	if(ret != -1) return ret;
	return ret = Left(i, j - 1);
}
int Right(int i, int j) {
	if(s[i][j] == '#') return j - 1;
	int &ret = right[i][j];
	if(ret != -1) return ret;
	return ret = Right(i, j + 1);
}
 
void print(ii oo) {
	cout<<"("<<(oo.first>>lg)<<", "<<(oo.first&((1<<lg)-1))<<", "<<oo.second<<")";
}
void printnode(int nd) {
	int x = nd >> lg;
	int y = nd & ((1<<lg)-1);
	cout<<ii(x, y);
}

int solve(int C, int F) { // dijkstra
	MEMSET(vis, 0);
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) e[node(i,j)] = 1e9;
	e[C] = 0;
	pq[0].push_back(C);
	for(int i = 0; i <= n * m; i++) {
		for(int u : pq[i]) {
			if(vis[u]) continue;
			vis[u] = 1;
			for(ii &b : g[u]) {
				int v = b.first, w = b.second;
				if(e[u] + w < e[v]) {
					e[v] = e[u] + w;
					pq[e[v]].push_back(v);
				}
			}
		}
		pq[i].clear();
	}
	return e[F];
}
 
int main () {
	// freopen("in", "r", stdin);
	MEMSET(up, -1);
	MEMSET(down, -1);
	MEMSET(left, -1);
	MEMSET(right, -1);
	cin(n), cin(m);
	for(int i=2; i<=n + 1; i++) scanf("%s", s[i]+2);
	for(int i = 1; i <= n + 2; i++) {
		for(int j = 1; j <= m + 2; j++) {
			if(i == 1 or j == 1 or i == n + 2 or j == m + 2) {
				s[i][j] = '#';
			}
		}
	}
	n += 2, m += 2;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(s[i][j] == '#') continue;
			int u, d, l, r;
			u = Up(i, j);
			d = Down(i, j);
			l = Left(i, j);
			r = Right(i, j);
			if(u!=i) g[node(i,j)].push_back(ii(node(u,j), min(i-u, 1+j-l, 1+r-j, 1+d-i))); // up
			if(d!=i) g[node(i,j)].push_back(ii(node(d,j), min(d-i, 1+j-l, 1+r-j, 1+i-u))); // down
			if(l!=j) g[node(i,j)].push_back(ii(node(i,l), min(j-l, 1+i-u, 1+d-i, 1+r-j))); // left
			if(r!=j) g[node(i,j)].push_back(ii(node(i,r), min(r-j, 1+i-u, 1+d-i, 1+j-l))); // right
			if(i-u > 1) g[node(i,j)].push_back(ii(node(i-1,j), 1)); // up
			if(d-i > 1) g[node(i,j)].push_back(ii(node(i+1,j), 1)); // down
			if(j-l > 1) g[node(i,j)].push_back(ii(node(i,j-1), 1)); // left
			if(r-j > 1) g[node(i,j)].push_back(ii(node(i,j+1), 1)); // right
		}
	}
	int C, F;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(s[i][j] == 'S') C = node(i,j);
			else if(s[i][j] == 'C') F = node(i,j);
		}
	}
	cout << solve(C,F) << endl;
	return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int myrand(int, int)':
portals.cpp:41:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
portals.cpp:41:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
portals.cpp: In function 'int main()':
portals.cpp:143:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  cin(n), cin(m);
        ^
portals.cpp:143:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
portals.cpp:144:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=2; i<=n + 1; i++) scanf("%s", s[i]+2);
                              ~~~~~^~~~~~~~~~~~~~
portals.cpp:34:14: warning: 'F' may be used uninitialized in this function [-Wmaybe-uninitialized]
 #define endl '\n'
              ^~~~
portals.cpp:171:9: note: 'F' was declared here
  int C, F;
         ^
portals.cpp:34:14: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
 #define endl '\n'
              ^~~~
portals.cpp:171:6: note: 'C' was declared here
  int C, F;
      ^

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