Submission #121865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
121865	2019-06-27T07:00:40 Z	Adhyyan1252	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	595 ms	90484 KB

tracks

#include<bits/stdc++.h>

using namespace std;

vector<vector<char> > g;
int h, w; 

using ii = pair<int, int>;


int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>h>>w;
	g = vector<vector<char> >(h, vector<char>(w));
	for(int i = 0; i < h; i++){
		string inp; cin>>inp;
		for(int j = 0; j < w; j++){
			if(inp[j] == '.'){
				g[i][j] = 2;
			}else if(inp[j] == 'F'){
				g[i][j] = 0;
			}else if(inp[j] == 'R'){
				g[i][j] = 1;
			}
		}
	}
	if(g[0][0] == 2){
		cout<<0<<endl;
		return 0;
	}

	if(g[0][0] != 0){ //flip if first one is 1
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				if(g[i][j] != 2) g[i][j] = 1 - g[i][j];
			}
		}
	}
	
	//top left cell is now 0
	vector<ii> active;
	active.push_back({0, 0});
	int ans = 0;
	g[0][0] = 3;
	vector<ii> del = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	while(!active.empty()){
		//cout<<"ANS "<<ans<<endl;
		vector<ii> nact;
		while(!active.empty()){
			int x = active.back().first, y = active.back().second;
			//cout<<"CUR "<<x<<" "<<y<<endl;
			active.pop_back();
			for(ii vec: del){
				int xd = x + vec.first, yd = y + vec.second;
				if(xd < 0 || xd >= h || yd < 0 || yd >= w) continue;
				//cout<<"CHECKING "<<xd<<" "<<yd<<" "<<(int)g[xd][yd]<<endl;
				if(g[xd][yd] == 3){ // means its visited
					
				}else if(g[xd][yd] == 2){ //empty
					
				}else if(g[xd][yd] == (ans%2)){
					active.push_back({xd, yd});
					//cout<<"PUSHED "<<xd<<" "<<yd<<endl;
					g[xd][yd] = 3;
				}else{
					nact.push_back({xd, yd});
					//cout<<"PUSHED D"<<xd<<" "<<yd<<endl;
					g[xd][yd] = 3;
				}
			}
		}
//		for(ii cur: nact){
//			cout<<"NACT "<<cur.first<<" "<<cur.second<<endl;
//		}
		ans++;
		active = nact; 
		nact.clear();
	}
	cout<<ans<<endl;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1148 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	7 ms	1060 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	10 ms	512 KB	Output is correct
12	Correct	6 ms	640 KB	Output is correct
13	Correct	4 ms	512 KB	Output is correct
14	Correct	4 ms	512 KB	Output is correct
15	Correct	10 ms	1004 KB	Output is correct
16	Correct	12 ms	1040 KB	Output is correct
17	Correct	9 ms	896 KB	Output is correct
18	Correct	16 ms	1080 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	640 KB	Output is correct
2	Correct	32 ms	3456 KB	Output is correct
3	Correct	238 ms	31892 KB	Output is correct
4	Correct	45 ms	7772 KB	Output is correct
5	Correct	264 ms	18140 KB	Output is correct
6	Correct	585 ms	63416 KB	Output is correct
7	Correct	4 ms	736 KB	Output is correct
8	Correct	4 ms	564 KB	Output is correct
9	Correct	4 ms	484 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	4 ms	640 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	33 ms	3556 KB	Output is correct
14	Correct	22 ms	2176 KB	Output is correct
15	Correct	23 ms	2304 KB	Output is correct
16	Correct	18 ms	1716 KB	Output is correct
17	Correct	80 ms	8440 KB	Output is correct
18	Correct	91 ms	8192 KB	Output is correct
19	Correct	45 ms	7844 KB	Output is correct
20	Correct	58 ms	7288 KB	Output is correct
21	Correct	148 ms	18768 KB	Output is correct
22	Correct	261 ms	18040 KB	Output is correct
23	Correct	158 ms	15904 KB	Output is correct
24	Correct	202 ms	18292 KB	Output is correct
25	Correct	434 ms	32036 KB	Output is correct
26	Correct	566 ms	90484 KB	Output is correct
27	Correct	457 ms	51704 KB	Output is correct
28	Correct	587 ms	63364 KB	Output is correct
29	Correct	595 ms	56128 KB	Output is correct
30	Correct	544 ms	58508 KB	Output is correct
31	Correct	471 ms	21944 KB	Output is correct
32	Correct	519 ms	70096 KB	Output is correct