Submission #58861

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58861	2018-07-19T16:37:51 Z	Mamnoon_Siam	Portals (BOI14_portals)	C++17	70 / 100	517 ms	242096 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(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

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.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	68216 KB	Output is correct
2	Correct	65 ms	68340 KB	Output is correct
3	Correct	59 ms	68408 KB	Output is correct
4	Correct	61 ms	68408 KB	Output is correct
5	Correct	66 ms	68512 KB	Output is correct
6	Correct	68 ms	68512 KB	Output is correct
7	Correct	61 ms	68512 KB	Output is correct
8	Correct	59 ms	68512 KB	Output is correct
9	Correct	60 ms	68512 KB	Output is correct
10	Correct	62 ms	68512 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	68512 KB	Output is correct
2	Correct	68 ms	68620 KB	Output is correct
3	Correct	68 ms	68644 KB	Output is correct
4	Correct	61 ms	68648 KB	Output is correct
5	Correct	57 ms	68652 KB	Output is correct
6	Correct	69 ms	68740 KB	Output is correct
7	Correct	60 ms	68740 KB	Output is correct
8	Correct	62 ms	68764 KB	Output is correct
9	Correct	67 ms	69136 KB	Output is correct
10	Correct	60 ms	69224 KB	Output is correct
11	Correct	66 ms	69224 KB	Output is correct
12	Correct	67 ms	69224 KB	Output is correct
13	Correct	57 ms	69224 KB	Output is correct
14	Correct	69 ms	69224 KB	Output is correct
15	Correct	61 ms	69224 KB	Output is correct
16	Correct	59 ms	69224 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	69224 KB	Output is correct
2	Correct	69 ms	69224 KB	Output is correct
3	Correct	59 ms	69224 KB	Output is correct
4	Correct	66 ms	69224 KB	Output is correct
5	Correct	77 ms	71112 KB	Output is correct
6	Correct	78 ms	71284 KB	Output is correct
7	Correct	81 ms	71592 KB	Output is correct
8	Correct	76 ms	71712 KB	Output is correct

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	71712 KB	Output is correct
2	Correct	66 ms	71712 KB	Output is correct
3	Correct	62 ms	71712 KB	Output is correct
4	Correct	60 ms	71712 KB	Output is correct
5	Correct	58 ms	71712 KB	Output is correct
6	Correct	61 ms	71712 KB	Output is correct
7	Correct	64 ms	71712 KB	Output is correct
8	Correct	69 ms	71712 KB	Output is correct
9	Correct	75 ms	71712 KB	Output is correct
10	Correct	73 ms	71712 KB	Output is correct
11	Correct	62 ms	71712 KB	Output is correct
12	Correct	72 ms	71712 KB	Output is correct
13	Correct	77 ms	71712 KB	Output is correct
14	Correct	94 ms	71712 KB	Output is correct
15	Correct	76 ms	71712 KB	Output is correct
16	Correct	70 ms	71820 KB	Output is correct
17	Correct	84 ms	71988 KB	Output is correct
18	Correct	94 ms	72652 KB	Output is correct
19	Correct	93 ms	73748 KB	Output is correct
20	Correct	81 ms	73920 KB	Output is correct
21	Correct	68 ms	73920 KB	Output is correct
22	Correct	84 ms	73920 KB	Output is correct
23	Correct	84 ms	73920 KB	Output is correct
24	Correct	88 ms	73920 KB	Output is correct
25	Correct	63 ms	73920 KB	Output is correct
26	Correct	60 ms	73920 KB	Output is correct
27	Correct	59 ms	73920 KB	Output is correct
28	Correct	87 ms	73920 KB	Output is correct

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	73920 KB	Output is correct
2	Correct	77 ms	73920 KB	Output is correct
3	Correct	66 ms	73920 KB	Output is correct
4	Correct	61 ms	73920 KB	Output is correct
5	Correct	56 ms	73920 KB	Output is correct
6	Correct	73 ms	73920 KB	Output is correct
7	Correct	61 ms	73920 KB	Output is correct
8	Correct	73 ms	73920 KB	Output is correct
9	Correct	71 ms	73920 KB	Output is correct
10	Correct	73 ms	73920 KB	Output is correct
11	Correct	70 ms	73920 KB	Output is correct
12	Correct	74 ms	73920 KB	Output is correct
13	Correct	72 ms	73920 KB	Output is correct
14	Correct	84 ms	73920 KB	Output is correct
15	Correct	73 ms	73920 KB	Output is correct
16	Correct	79 ms	73920 KB	Output is correct
17	Correct	72 ms	73920 KB	Output is correct
18	Correct	86 ms	73920 KB	Output is correct
19	Correct	82 ms	74344 KB	Output is correct
20	Correct	89 ms	74384 KB	Output is correct
21	Correct	77 ms	74384 KB	Output is correct
22	Correct	68 ms	74384 KB	Output is correct
23	Correct	69 ms	74384 KB	Output is correct
24	Runtime error	517 ms	242096 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-