Submission #1109850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109850		raspy	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	799 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) continue;
		dfs(ni, nj, nc, n, m);
	}
}

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

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