Submission #471401

#	Time	Username	Problem	Language	Result	Execution time	Memory
471401		YoRepi7	Tracks in the Snow (BOI13_tracks)	C++17	36.77 / 100	2089 ms	901172 KiB

tracks

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
using vpl = vector<pl>;
using vpi = vector<pi>;
using vc = vector<char>;
using vs = vector<string>;
 
#define forn(i, n) for(int i = 0; i < n; i++)
#define rofn(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, b, a) for(int i = b; i >= a; i--)
#define TRAV(a, x) for(auto& a: x)
#define ABC(c) for(char c = 'a'; c <= 'z'; c++)
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsor(x) sort(all(x), greater<int>())
#define pb push_back
#define mp make_pair
#define ins insert
#define ub upper_bound
#define lb lower_bound
#define len(x) (int)(x).length()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define dbg(x) TRAV(a, x) cout << a << " "
#define print(x) cout << x << endl
#define traverse(x) TRAV(a, x) cout << a.f << " " << a.s << endl
#define readvi(a, n) forn(i, n) cin >> a[i]
#define readvpi(a, n) forn(i, n) cin >> a[i].f >> a[i].s
#define gcd(a, b) __gcd(a, b)

const int MAXN = 4000, INF = 1e9;

char grid[MAXN][MAXN]; int vis[MAXN][MAXN], comp[MAXN][MAXN], h, w, cur;

int xDir[4] = {1, -1, 0, 0}, yDir[4] = {0, 0, 1, -1};

bool vis1[MAXN * MAXN + 1];

void floodfill(int i, int j, char animal){
	if(i >= h || j >= w || i < 0 || j < 0 || grid[i][j] != animal || vis[i][j]){
		return;
	}
	vis[i][j] = true;
	comp[i][j] = cur;
	forn(k, 4){
		floodfill(i + xDir[k], j + yDir[k], animal);
	}
}

void solve(){
	cin >> h >> w;
	forn(i, h){
		forn(j, w){
			cin >> grid[i][j];
		}
	}
	cur = 1;
	forn(i, h){
		forn(j, w){
			if(grid[i][j] != '.' && !vis[i][j]){
				floodfill(i, j, grid[i][j]);
				++cur;
			}
		}
	}
	vi adj[cur + 1], dist(cur + 1, INF);
	forn(i, h){
		forn(j, w){
			if(comp[i][j]){
				forn(k, 4){
					int x = i + xDir[k], y = j + yDir[k];
					if(x && y && comp[x][y] && (comp[x][y] != comp[i][j])){
						adj[comp[i][j]].pb(comp[x][y]);
						adj[comp[x][y]].pb(comp[i][j]);
					}
				}
			}
		}
	}
	queue<int> q;
	q.push(comp[0][0]);
	dist[comp[0][0]] = 0;
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		if(vis1[cur]){
			continue;
		}
		vis1[cur] = true;
		TRAV(a, adj[cur]){
			if(dist[a] > dist[cur] + 1){
				dist[a] = dist[cur] + 1;
			}
			q.push(a);
		}
	}
	int ans = 0;
	FOR(i, 1, cur){
		ans = max(ans, dist[i]);
	}
	cout << ++ans << endl;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	// int t; cin >> t;
	// forn(i, t){
	// 	solve();
	// }
	solve();
}

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