oj.uz

Submission #97132

# Submission time Handle Problem Language Result Execution time Memory
97132 2019-02-14T03:34:53 Z maruii None (JOI16_skating) C++17
13 / 100
 1081 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;
int R, C, dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
char A[1005][1005];
using pii = pair<int, int>;
struct Node{
	int x,y,dist;
	vector<pii> vec;
};
queue<Node> q;
int main(){
	scanf("%d%d",&R,&C);
	for(int i=0; i<R; ++i)
		scanf("%s",A[i]);
	Node st;
	for(int i=0; i<R; ++i) for(int j=0; j<C; ++j) if(A[i][j]=='#') st.vec.push_back({i, j});
	st.dist = 0;
	int ex, ey;
	scanf("%d%d",&st.x,&st.y), --st.x, --st.y;
	scanf("%d%d",&ex,&ey), --ex, --ey;
	sort(st.vec.begin(), st.vec.end());
	q.push(st);
	while(q.size()){
		auto cur = q.front(); q.pop();
		if(cur.x == ex && cur.y == ey) return !printf("%d",cur.dist);
		for(int i=0; i<4; ++i){
			int j;
			for(j=0; j<1000; ++j){
				int nx = cur.x+dx[i]*j, ny = cur.y+dy[i]*j;
				if(nx<0 || ny<0 || nx>=R || ny>=C || *lower_bound(cur.vec.begin(), cur.vec.end(), pii(nx, ny))==pii(nx, ny)) break;
			}
			if(j==0) break;
			if(j>1){
				--j;
				auto t = cur;
				t.x += dx[i]*j, t.y += dy[i]*j, ++t.dist;
				int ub = upper_bound(t.vec.begin(), t.vec.end(), pii(cur.x, cur.y))-t.vec.begin();
				t.vec.push_back({0, 0});
				for(int i=t.vec.size()-1; i>ub; --i) t.vec[i] = t.vec[i-1];
				t.vec[ub] = {cur.x, cur.y};
				q.push(t);
			}
		}
	}
	printf("-1");
	return 0;
}

Compilation message

skating.cpp: In function 'int main()':
skating.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&R,&C);
  ~~~~~^~~~~~~~~~~~~~
skating.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",A[i]);
   ~~~~~^~~~~~~~~~~
skating.cpp:19:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&st.x,&st.y), --st.x, --st.y;
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
skating.cpp:20:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&ex,&ey), --ex, --ey;
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 12 ms 2816 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 1081 ms 51036 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 12 ms 2816 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 1081 ms 51036 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Runtime error 805 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 12 ms 2816 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 1081 ms 51036 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Runtime error 805 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -