oj.uz

Submission #1035863

# Submission time Handle Problem Language Result Execution time Memory
1035863 2024-07-26T16:59:23 Z Callie Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 903 ms 136376 KB 
//Tracks in the Snow
#include <iostream>
#include <vector>
#include <deque>

#define pr pair<int, int>
#define prr pair<pr, int>
#define f first
#define s second
using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[5] = {0, 0, 1, -1};

int main() {
	int height, width;
	cin >> height >> width;
	vector<vector<int> > map(height, vector<int> (width, 0));
	
	for(int i = 0; i < height; i++) {
		string curr;
		cin >> curr;
		for(int j = 0; j < width; j++) {
			if(curr.substr(j, 1) == ".") map[i][j] = 0;
			else if(curr.substr(j, 1) == "R") map[i][j] = 1;
			else map[i][j] = 2;
			
			//cout << curr << " ";
		}
		//cout << endl;
	}
	
	/*for(int i = 0; i < height; i++) {
		for(int j = 0; j < width; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}*/
	
	deque<prr> q;
	prr p;
	p.f.f = 0;
	p.f.s = 0;
	p.s = map[0][0];
	q.push_back(p);
	
	int count = 0;
	int track = -1;
	vector<vector<bool> > visited(height, vector<bool>(width, false));
	while(!q.empty()) {
		prr curr = q.front();
		q.pop_front();
		
		int x = curr.f.f;
		int y = curr.f.s;
		int type = curr.s;
		//cout << x << " " << y << " " << type << endl;
		
		if(type != track) {
			count++;
			track = type;
		}
		
		for(int i = 0; i < 4; i++) {
			int nextx = x + dx[i];
			int nexty = y + dy[i];
			
			if(nextx < 0 || nextx >= height) continue;
			if(nexty < 0 || nexty >= width) continue;
			if(visited[nextx][nexty]) continue;
			
			visited[nextx][nexty] = true;
			int nexttype = map[nextx][nexty];
			if(nexttype == 0) continue;
			
			prr n;
			n.f.f = nextx;
			n.f.s = nexty;
			n.s = nexttype;
			if(nexttype == type) {
				q.push_front(n);
			}
			else q.push_back(n);
		}
	}
	
	cout << count << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1628 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 1372 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 6 ms 860 KB Output is correct
13 Correct 4 ms 860 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 14 ms 1688 KB Output is correct
16 Correct 15 ms 1768 KB Output is correct
17 Correct 12 ms 1628 KB Output is correct
18 Correct 9 ms 1324 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 68 ms 8216 KB Output is correct
3 Correct 526 ms 80820 KB Output is correct
4 Correct 132 ms 19280 KB Output is correct
5 Correct 344 ms 45604 KB Output is correct
6 Correct 888 ms 101060 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 3 ms 704 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 1076 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 84 ms 8360 KB Output is correct
14 Correct 66 ms 4944 KB Output is correct
15 Correct 44 ms 5520 KB Output is correct
16 Correct 31 ms 3580 KB Output is correct
17 Correct 184 ms 20836 KB Output is correct
18 Correct 158 ms 20564 KB Output is correct
19 Correct 129 ms 19280 KB Output is correct
20 Correct 121 ms 17580 KB Output is correct
21 Correct 319 ms 47228 KB Output is correct
22 Correct 379 ms 45732 KB Output is correct
23 Correct 357 ms 39376 KB Output is correct
24 Correct 325 ms 46168 KB Output is correct
25 Correct 780 ms 80980 KB Output is correct
26 Correct 619 ms 136376 KB Output is correct
27 Correct 797 ms 120136 KB Output is correct
28 Correct 901 ms 101064 KB Output is correct
29 Correct 903 ms 98748 KB Output is correct
30 Correct 853 ms 105724 KB Output is correct
31 Correct 661 ms 52720 KB Output is correct
32 Correct 779 ms 103572 KB Output is correct