Submission #535530

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535530	2022-03-10T12:56:13 Z	Koful123	Tracks in the Snow (BOI13_tracks)	C++17	75.9375 / 100	2000 ms	890696 KB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define endl "\n"
#define mod 1000000007
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int N = 4005;
int vis[N][N],cnt,n,m,ans;
string s[N];
queue<pair<int,int>> q,tmp;

void dfs(int x,int y,char c){
	if(x > n || y > m || y < 0 || x < 0) return;
	if(vis[x][y]) return;
	if(!vis[x][y] && s[x][y] != c){
		tmp.push({x,y});
		return;
	}

	if(!vis[x][y]){
		vis[x][y] = 1;
		cnt++;
	}

	dfs(x+1,y,c);
	dfs(x,y+1,c);
	dfs(x,y-1,c);
	dfs(x-1,y,c);
}

void solve(){		

	cin >> n >> m;

	for(int i=0;i<n;i++)
		cin >> s[i];

	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(s[i][j] == '.'){
				vis[i][j] = 1;
				cnt++;
			}
		}
	}

	char c = s[n-1][m-1];
	q.push({n-1,m-1});

	while(cnt != n*m){
		while(q.size()){
			auto tp = q.front();
			dfs(tp.ff,tp.ss,c);
			q.pop();
		}

		while(tmp.size()){
			q.push(tmp.front());
			tmp.pop();
		}

		if(c == 'F') c = 'R';
		else c = 'F';
		ans++;
	}

	cout << ans << endl;
}

signed main(){

	ios_base::sync_with_stdio(0);	
	cin.tie(0);	

	#ifndef ONLINE_JUDGE
	//	freopen("in.txt","r",stdin);
	//	freopen("out.txt","w",stdout);
	#endif
 
	int t = 1;
	//cin >> t;

 	for(int i=1;i<=t;i++){
 		solve();
	}

	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	4812 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	8 ms	5460 KB	Output is correct
5	Correct	3 ms	2340 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	852 KB	Output is correct
10	Correct	3 ms	2004 KB	Output is correct
11	Correct	3 ms	2388 KB	Output is correct
12	Correct	6 ms	2540 KB	Output is correct
13	Correct	3 ms	2388 KB	Output is correct
14	Correct	2 ms	2388 KB	Output is correct
15	Correct	14 ms	4864 KB	Output is correct
16	Correct	15 ms	4820 KB	Output is correct
17	Correct	9 ms	4556 KB	Output is correct
18	Correct	10 ms	5460 KB	Output is correct

Subtask #2

45.9375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	16332 KB	Output is correct
2	Correct	58 ms	19592 KB	Output is correct
3	Execution timed out	2093 ms	126412 KB	Time limit exceeded
4	Correct	83 ms	41516 KB	Output is correct
5	Execution timed out	2086 ms	58228 KB	Time limit exceeded
6	Correct	817 ms	261648 KB	Output is correct
7	Correct	609 ms	17108 KB	Output is correct
8	Correct	30 ms	16344 KB	Output is correct
9	Correct	6 ms	1396 KB	Output is correct
10	Correct	2 ms	980 KB	Output is correct
11	Correct	8 ms	16856 KB	Output is correct
12	Correct	52 ms	1236 KB	Output is correct
13	Correct	55 ms	19660 KB	Output is correct
14	Correct	27 ms	12308 KB	Output is correct
15	Execution timed out	2085 ms	13524 KB	Time limit exceeded
16	Correct	31 ms	8076 KB	Output is correct
17	Correct	119 ms	44932 KB	Output is correct
18	Execution timed out	2075 ms	44252 KB	Time limit exceeded
19	Correct	68 ms	41548 KB	Output is correct
20	Execution timed out	2094 ms	36740 KB	Time limit exceeded
21	Execution timed out	2096 ms	88340 KB	Time limit exceeded
22	Execution timed out	2088 ms	58464 KB	Time limit exceeded
23	Correct	284 ms	80104 KB	Output is correct
24	Execution timed out	2087 ms	75024 KB	Time limit exceeded
25	Execution timed out	2065 ms	144016 KB	Time limit exceeded
26	Correct	805 ms	890696 KB	Output is correct
27	Correct	860 ms	780348 KB	Output is correct
28	Correct	802 ms	261880 KB	Output is correct
29	Execution timed out	2087 ms	281616 KB	Time limit exceeded
30	Correct	780 ms	368948 KB	Output is correct
31	Correct	746 ms	107184 KB	Output is correct
32	Execution timed out	2115 ms	484728 KB	Time limit exceeded