Submission #1109855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109855		raspy	Tracks in the Snow (BOI13_tracks)	C++17	23.02 / 100	2118 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 a[4001][4001];
int comp[4001][4001];
vi graf[20000001];
set<ii> pov;
vector<ii> pr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void dfs(int i, int j, int nc, int n, int m)
{
	if (comp[i][j]) return;
	comp[i][j] = nc;
	for (ii d : pr)
	{
		int ni = i+d.f, nj = j+d.s;
		if (ni < 0 || nj < 0 || nj >= m || ni >= n || a[ni][nj] != a[i][j]) continue;
		dfs(ni, nj, nc, n, m);
	}
}

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

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;
		}
	int nc = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (a[i][j])
				dfs(i, j, nc++, n, m);
	// for (int i = 0; i < n; i++)
	// 	for (int j = 0; j < m; j++)
	// 		cout << comp[i][j] << " \n"[j == m-1];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 0) continue;
			for (ii d : pr)
			{
				int ni = i+d.f, nj = j+d.s;
				if (ni < 0 || nj < 0 || nj >= m || ni >= n || comp[ni][nj] == comp[i][j] || !a[ni][nj])
					continue;
				if (pov.find({comp[ni][nj], comp[i][j]}) != pov.end()) continue;
				// cout << a[i][j] << " " << a[ni][nj] << " " << comp[i][j] << " " << comp[ni][nj] << "\n";
				pov.insert({comp[ni][nj], comp[i][j]});
				pov.insert({comp[i][j], comp[ni][nj]});
				graf[comp[ni][nj]].pb(comp[i][j]);
				graf[comp[i][j]].pb(comp[ni][nj]);
			}
		}
	cout << dfs1(comp[0][0]) << "\n";
	return 0;
}

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