Submission #1109844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109844		raspy	Tracks in the Snow (BOI13_tracks)	C++17	23.02 / 100	2109 ms	1048576 KiB

tracks

#include <bits/stdc++.h>

// #define int long long
#define vi vector<int>
#define ii pair<int, int>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define P 31
#define mod 1'000'000'007
#define inf 1'000'000'000'000
#define pb push_back
#define str string
#define sz(x) (x).size()
#define vvi vector<vi>
#define fun function
#define oopt cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define file freopen("problemname.in", "r", stdin); freopen("pr.out", "w", stdout);
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;

using namespace std;
template <class T, int SZ> using arr = array<T, SZ>;

int p[16000005];
int a[4001][4001];
bool ob[16000005];
set<int> pov[16000005];

int par(int x) {return p[x] = (p[x] == x ? x : par(p[x]));};

void zd(int x, int y)
{
	x = par(x);
	y = par(y);
	if (x == y) return;
	if (pov[x].size() < pov[y].size())
		swap(x, y);
	for (int v : pov[y])
		pov[x].insert(v);
	pov[y].clear();
	p[y] = x;
}

int dfs(int u, int p = -1)
{
	// cout << u << " <- " << p << "\n";
	int rez = 0;
	for (int v : pov[u])
		if (v != p)
			rez = max(rez, dfs(v, u));
	return rez+1;
}

vector<ii> pr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

signed main()
{
	oopt;
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			char c;
			cin >> c;
			if (c == 'F') a[i][j] = 1;
			else if (c == 'R') a[i][j] = 2;
			p[i*m+j] = i*m+j;
		}
	queue<ii> q;
	q.push({0, 0});
	while (q.size())
	{
		ii t = q.front();
		q.pop();
		int i = t.f, j = t.s;
		int x = i*m+j, y = 0;
		for (ii d : pr)
		{
			int ni = i+d.f, nj = j+d.s;
			y = ni*m+nj;
			if (ni < 0 || nj < 0 || ni > n || nj > m || ob[par(y)] || a[ni][nj] == 0) continue;
			if (a[ni][nj] != a[i][j]) continue;
			zd(x, y);
			ob[par(y)] = 1;
			q.push({ni, nj});
		}
		for (ii d : pr)
		{
			int ni = i+d.f, nj = j+d.s;
			y = ni*m+nj;
			if (ni < 0 || nj < 0 || ni > n || nj > m || ob[par(y)] || a[ni][nj] == 0) continue;
			ob[par(y)] = 1;
			// cout << par(x) << " " << par(y) << "t\n";
			pov[par(x)].insert(par(y));
			pov[par(y)].insert(par(x));
			q.push({ni, nj});
		}
	}
	cout << dfs(0) << "\n";
	return 0;
}

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