Submission #1126457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126457		Agageldi	Tracks in the Snow (BOI13_tracks)	C++20	5.52 / 100	2099 ms	228016 KiB

tracks

/*
ID: agageld1
LANG: C++17
TASK:
*/
#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++)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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 () {
	//freopen("txt.in","r",stdin);
	//freopen("txt.out","w",stdout);
	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(a[x1][x2] != a[y1][y2]) {
				if(!tr)	tr = 1;
				h.push({x1,x2});
			}
			else q.push({x1,x2});
		}
		a[y1][y2] = '.';
		if(q.empty()) {
			cnt += tr;
			while(!h.empty()) {
				q.push({h.front().ff,h.front().ss});
				h.pop();
			}
		}
	}
	cout << cnt << '\n';
}

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