Submission #1126464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126464		Agageldi	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1269 ms	171508 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define N 400005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define rep(c, a, b) for(c = a; c <= b; c++)

int c[] = {0,0,-1,1};
int d[] = {1,-1,0,0};
ll n, m, cnt = 0, vis[5000][5000];
char a[5000][5000];
queue <pair<int,int>> q, h;
 
int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i= 1;i<=n;i++) {
		for(int j =1;j<=m;j++) {
			cin >> a[i][j];
		}
	}
	q.push({1,1});
	cnt = 1;
	while(!q.empty()) {
		int y1 = q.front().ff,y2 = q.front().ss;
		bool tr = 0;
		q.pop();
		for(int i = 0; i < 4; i++) {
			int x1 = y1 + c[i], x2 = y2 + d[i];
			if(x1 <= 0 || x2 <= 0 || x1 > n || x2 > m || a[x1][x2] == '.') continue;
			if(vis[x1][x2]) continue;
			vis[x1][x2] = 1;
			if(a[x1][x2] != a[y1][y2]) {
				h.push({x1,x2});
			}
			else q.push({x1,x2});
		}
		a[y1][y2] = '.';
		if(q.empty()) {
			if(!h.empty())cnt++;
			while(!h.empty()) {
				q.push({h.front().ff,h.front().ss});
				h.pop();
			}
			cout << '\n';
		}
	}
	cout << cnt << '\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70