oj.uz

Submission #39313

# Submission time Handle Problem Language Result Execution time Memory
39313 2018-01-11T07:09:30 Z Mamnoon_Siam Portal (COCI17_portal) C++14
120 / 120
 136 ms 26384 KB 
#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)

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];
int link[maxn*maxn];

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 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;
				link[x] = u;
				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;
	}
	/*cout<<e[node(8, 6)]<<endl;
	cout<<e[node(5, 6)]<<endl;
	cout<<e[node(5, 7)]<<endl;
	cout<<e[node(4, 7)]<<endl;
	cout<<e[node(4, 9)]<<endl;
	int now = F;
	while(now != C) {
		cout<<">> "; printnode(now); cout<<endl;
		now = link[now];
	}
	{
		int me = node(4, 7);
		for(auto x : v[me]) {
			printnode(x.first);
			cout<<" = "<<x.second<<endl;
		}
	}*/
	return 0;
}

Compilation message

portal.cpp: In function 'int main()':
portal.cpp:122:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  cin(n), cin(m);
                ^
portal.cpp:122:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
portal.cpp:123: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:173:18: warning: 'F' may be used uninitialized in this function [-Wmaybe-uninitialized]
   cout<<solve(C,F)<<endl;
                  ^
portal.cpp:173:18: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
portal.cpp:152: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:151: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:150: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:149: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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11412 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11412 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11412 KB Output is correct
2 Correct 0 ms 11412 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11412 KB Output is correct
2 Correct 0 ms 11412 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11412 KB Output is correct
2 Correct 0 ms 11412 KB Output is correct
3 Correct 0 ms 11412 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12468 KB Output is correct
2 Correct 0 ms 12072 KB Output is correct
3 Correct 6 ms 12780 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14052 KB Output is correct
2 Correct 3 ms 11808 KB Output is correct
3 Correct 19 ms 13476 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 21148 KB Output is correct
2 Correct 53 ms 15636 KB Output is correct
3 Correct 53 ms 16908 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22332 KB Output is correct
2 Correct 33 ms 17880 KB Output is correct
3 Correct 63 ms 20528 KB Output is correct
4 Correct 63 ms 18320 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 25704 KB Output is correct
2 Correct 39 ms 17880 KB Output is correct
3 Correct 123 ms 26384 KB Output is correct
4 Correct 136 ms 26112 KB Output is correct