Submission #471401

#TimeUsernameProblemLanguageResultExecution timeMemory
471401YoRepi7Tracks in the Snow (BOI13_tracks)C++17
36.77 / 100
2089 ms901172 KiB
#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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...