Submission #58862

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58862	2018-07-19T16:38:35 Z	Mamnoon_Siam	Portals (BOI14_portals)	C++17	70 / 100	1000 ms	50392 KB

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(v) v.begin(), v.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 = 1000;
 
#define lg 10
#define node(x, y) (((x)<<(lg))|(y))
 
vector<pair<int, int> > v[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];

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
	min_pq<ii> pq;
	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.push(ii(0,C));
	while(!pq.empty()) {
		int u = pq.top().second; pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto b : v[u]) {
			int x = b.first, w = b.second;
			if(e[u]+w < e[x]) {
				e[x] = e[u]+w;
				link[x] = u;
				pq.push(ii(e[x], x));
			}
		}
	}
	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) v[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) v[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) v[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) v[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) v[node(i,j)].push_back(ii(node(i-1,j), 1)); // up
			if(d-i > 1) v[node(i,j)].push_back(ii(node(i+1,j), 1)); // down
			if(j-l > 1) v[node(i,j)].push_back(ii(node(i,j-1), 1)); // left
			if(r-j > 1) v[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

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:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  cin(n), cin(m);
        ^
portals.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
portals.cpp:143: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:170: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:170:6: note: 'C' was declared here
  int C, F;
      ^

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	44152 KB	Output is correct
2	Correct	49 ms	44264 KB	Output is correct
3	Correct	39 ms	44344 KB	Output is correct
4	Correct	38 ms	44344 KB	Output is correct
5	Correct	45 ms	44344 KB	Output is correct
6	Correct	38 ms	44344 KB	Output is correct
7	Correct	37 ms	44344 KB	Output is correct
8	Correct	40 ms	44344 KB	Output is correct
9	Correct	45 ms	44420 KB	Output is correct
10	Correct	38 ms	44420 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	44420 KB	Output is correct
2	Correct	44 ms	44420 KB	Output is correct
3	Correct	48 ms	44420 KB	Output is correct
4	Correct	46 ms	44420 KB	Output is correct
5	Correct	47 ms	44420 KB	Output is correct
6	Correct	52 ms	44420 KB	Output is correct
7	Correct	43 ms	44460 KB	Output is correct
8	Correct	40 ms	44460 KB	Output is correct
9	Correct	42 ms	44980 KB	Output is correct
10	Correct	41 ms	45112 KB	Output is correct
11	Correct	45 ms	45112 KB	Output is correct
12	Correct	46 ms	45112 KB	Output is correct
13	Correct	47 ms	45112 KB	Output is correct
14	Correct	39 ms	45112 KB	Output is correct
15	Correct	40 ms	45112 KB	Output is correct
16	Correct	40 ms	45112 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	45112 KB	Output is correct
2	Correct	39 ms	45112 KB	Output is correct
3	Correct	45 ms	45112 KB	Output is correct
4	Correct	50 ms	45112 KB	Output is correct
5	Correct	52 ms	47220 KB	Output is correct
6	Correct	54 ms	47476 KB	Output is correct
7	Correct	55 ms	47684 KB	Output is correct
8	Correct	59 ms	47684 KB	Output is correct

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	47684 KB	Output is correct
2	Correct	50 ms	47684 KB	Output is correct
3	Correct	41 ms	47684 KB	Output is correct
4	Correct	45 ms	47684 KB	Output is correct
5	Correct	48 ms	47684 KB	Output is correct
6	Correct	40 ms	47684 KB	Output is correct
7	Correct	42 ms	47684 KB	Output is correct
8	Correct	40 ms	47684 KB	Output is correct
9	Correct	42 ms	47684 KB	Output is correct
10	Correct	41 ms	47684 KB	Output is correct
11	Correct	46 ms	47684 KB	Output is correct
12	Correct	41 ms	47684 KB	Output is correct
13	Correct	42 ms	47684 KB	Output is correct
14	Correct	51 ms	47684 KB	Output is correct
15	Correct	54 ms	47696 KB	Output is correct
16	Correct	54 ms	47864 KB	Output is correct
17	Correct	61 ms	48116 KB	Output is correct
18	Correct	74 ms	48740 KB	Output is correct
19	Correct	72 ms	49936 KB	Output is correct
20	Correct	62 ms	49936 KB	Output is correct
21	Correct	57 ms	49936 KB	Output is correct
22	Correct	66 ms	49936 KB	Output is correct
23	Correct	65 ms	49936 KB	Output is correct
24	Correct	70 ms	49936 KB	Output is correct
25	Correct	39 ms	49936 KB	Output is correct
26	Correct	45 ms	49936 KB	Output is correct
27	Correct	42 ms	49936 KB	Output is correct
28	Correct	54 ms	49936 KB	Output is correct

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	49936 KB	Output is correct
2	Correct	40 ms	49936 KB	Output is correct
3	Correct	40 ms	49936 KB	Output is correct
4	Correct	42 ms	49936 KB	Output is correct
5	Correct	41 ms	49936 KB	Output is correct
6	Correct	45 ms	49936 KB	Output is correct
7	Correct	41 ms	49936 KB	Output is correct
8	Correct	39 ms	49936 KB	Output is correct
9	Correct	41 ms	49936 KB	Output is correct
10	Correct	40 ms	49936 KB	Output is correct
11	Correct	40 ms	49936 KB	Output is correct
12	Correct	44 ms	49936 KB	Output is correct
13	Correct	44 ms	49936 KB	Output is correct
14	Correct	62 ms	49936 KB	Output is correct
15	Correct	69 ms	49936 KB	Output is correct
16	Correct	60 ms	49936 KB	Output is correct
17	Correct	71 ms	49936 KB	Output is correct
18	Correct	66 ms	49936 KB	Output is correct
19	Correct	76 ms	50276 KB	Output is correct
20	Correct	79 ms	50392 KB	Output is correct
21	Correct	62 ms	50392 KB	Output is correct
22	Correct	52 ms	50392 KB	Output is correct
23	Correct	63 ms	50392 KB	Output is correct
24	Execution timed out	1072 ms	50392 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-