Submission #535533

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535533	2022-03-10T12:57:34 Z	Koful123	Tracks in the Snow (BOI13_tracks)	C++17	71.5625 / 100	2000 ms	1048576 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;

inline 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	13 ms	3796 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	4948 KB	Output is correct
5	Correct	2 ms	2004 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	2 ms	1748 KB	Output is correct
11	Correct	3 ms	2516 KB	Output is correct
12	Correct	6 ms	2132 KB	Output is correct
13	Correct	4 ms	2004 KB	Output is correct
14	Correct	2 ms	2004 KB	Output is correct
15	Correct	11 ms	3760 KB	Output is correct
16	Correct	18 ms	3796 KB	Output is correct
17	Correct	10 ms	3668 KB	Output is correct
18	Correct	9 ms	4988 KB	Output is correct

Subtask #2

41.5625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	15956 KB	Output is correct
2	Correct	46 ms	13588 KB	Output is correct
3	Execution timed out	2079 ms	76532 KB	Time limit exceeded
4	Correct	64 ms	26900 KB	Output is correct
5	Execution timed out	2075 ms	40704 KB	Time limit exceeded
6	Correct	709 ms	217952 KB	Output is correct
7	Correct	409 ms	16896 KB	Output is correct
8	Correct	27 ms	15956 KB	Output is correct
9	Correct	4 ms	1152 KB	Output is correct
10	Correct	2 ms	980 KB	Output is correct
11	Correct	9 ms	16464 KB	Output is correct
12	Correct	41 ms	1188 KB	Output is correct
13	Correct	46 ms	13532 KB	Output is correct
14	Correct	20 ms	8788 KB	Output is correct
15	Execution timed out	2090 ms	9556 KB	Time limit exceeded
16	Correct	26 ms	5588 KB	Output is correct
17	Correct	95 ms	29004 KB	Output is correct
18	Execution timed out	2068 ms	28604 KB	Time limit exceeded
19	Correct	54 ms	26956 KB	Output is correct
20	Execution timed out	2097 ms	24740 KB	Time limit exceeded
21	Execution timed out	2087 ms	57996 KB	Time limit exceeded
22	Execution timed out	2059 ms	40440 KB	Time limit exceeded
23	Correct	221 ms	48616 KB	Output is correct
24	Execution timed out	2095 ms	50932 KB	Time limit exceeded
25	Execution timed out	2090 ms	81312 KB	Time limit exceeded
26	Runtime error	549 ms	1048576 KB	Execution killed with signal 9
27	Correct	982 ms	1031824 KB	Output is correct
28	Correct	673 ms	217888 KB	Output is correct
29	Execution timed out	2094 ms	250116 KB	Time limit exceeded
30	Execution timed out	2102 ms	386320 KB	Time limit exceeded
31	Correct	619 ms	63524 KB	Output is correct
32	Execution timed out	2125 ms	588056 KB	Time limit exceeded