Submission #39312

#	Time	Username	Problem	Language	Result	Execution time	Memory
39312		Mamnoon_Siam	Portal (COCI17_portal)	C++14	36 / 120	123 ms	24828 KiB

portal

#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;
}

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(b_,c_)); }
template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(b_,c_)); }
//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)

const int maxn = 516;

#define lg 9
#define node(x, y) (((x)<<(lg))|(y))

vector<pair<int, int> > v[node(500, 500)+10];
int e[maxn*maxn], vis[maxn*maxn], n, m;
char s[maxn][maxn];

void print(ii oo) {
	cout<<"("<<(oo.first>>lg)<<", "<<(oo.first&((1<<lg)-1))<<", "<<oo.second<<")";
}

int dfs(int now, int to) { // to check if connected
	if(now == to) return 1;
	vis[now] = 1;
	for(auto x : v[now]) {
		int b = x.first;
		if(!vis[b]) {
			int ret = dfs(b, to);
			if(ret) return ret;
		}
	} return 0;
}

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;
				pq.push(ii(e[x], x));
			}
		}
	}
	return e[F];
}

int main () {
	//readfile("input.in");
	cin(n), cin(m);
	for(int i=1; i<=n; i++) scanf("%s", s[i]+1);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(s[i][j] == '#') continue;
			int u, d, l, r;
			for(int k=i-1; k>=0; k--) { // up
				if(s[k][j] == '#') {
					u = k+1; break;
				}
			}
			for(int k=i+1; k<=n; k++) { // down
				if(s[k][j] == '#') {
					d = k-1; break;
				}
			}
			for(int k=j-1; k>=0; k--) { // left
				if(s[i][k] == '#') {
					l = k+1; break;
				}
			}
			for(int k=j+1; k<=m; k++) { // right
				if(s[i][k] == '#') {
					r = k-1; break;
				}
			}
			//cout<<"("<<i<<", "<<j<<")"<<" :: "<<u<<' '<<d<<' '<<l<<' '<<r<<endl;
			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
			//cout<<"["<<i<<", "<<j<<"]"<<" :: ";
			//for(auto b : v[node(i,j)]) print(b), cout<<", "; cout<<endl;
		}
	}
	int C, F;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(s[i][j] == 'C') C = node(i,j);
			else if(s[i][j] == 'F') F = node(i,j);
		}
	}
	int ret = dfs(C,F);
	if(!ret) {
		cout<<"nemoguce"<<endl;
	}
	else {
		cout<<solve(C,F)<<endl;
	}
	return 0;
}

Compilation message (stderr)

portal.cpp: In function 'int main()':
portal.cpp:112:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  cin(n), cin(m);
                ^
portal.cpp:112:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
portal.cpp:113:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%s", s[i]+1);
                                             ^
portal.cpp:163:18: warning: 'F' may be used uninitialized in this function [-Wmaybe-uninitialized]
   cout<<solve(C,F)<<endl;
                  ^
portal.cpp:163:18: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
portal.cpp:142:53: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
    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
                                                     ^
portal.cpp:141:53: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
    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
                                                     ^
portal.cpp:140:53: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
    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
                                                     ^
portal.cpp:139:53: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
    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
                                                     ^

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 0 / 12
• Subtask 4: 12 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12