Submission #708122

#	Time	Username	Problem	Language	Result	Execution time	Memory
708122		tgp072	Tracks in the Snow (BOI13_tracks)	C++17	19.79 / 100	2119 ms	838448 KiB

tracks

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <tuple>
#include <numeric>
#include <climits>
#include <bitset>
#include <iomanip>
#include <random>
#include <ctime>
using namespace std;

typedef int ll;

ll max(ll a, ll b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

ll min(ll a, ll b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}

const ll MAXN = 4001;
const ll MAXM = 2097153;
const ll MOD = 1e9 + 7;
const ll INF = 1e7;

ll h, w;
ll dr[4] = {1, 0, -1, 0};
ll dc[4] = {0, 1, 0, -1};
ll mark[MAXN][MAXN];
char grid[MAXN][MAXN];

ll cnt;
void dfs(ll row, ll col) {
    for (ll k = 0; k < 4; k++) {
        ll nr = row + dr[k];
        ll nc = col + dc[k];
        if (nr >= 0 && nr < h && nc >= 0 && nc < w && grid[nr][nc] == grid[row][col] && mark[nr][nc] == 0) {
            mark[nr][nc] = cnt;
            dfs(nr, nc);
        }
    }
}

void solve(ll ca) {
    cin >> h >> w;
    
    for (ll i = 0; i < h; i++) {
        for (ll j = 0; j < w; j++) {
            cin >> grid[i][j];
        }
    }
    
    cnt = 1;
    for (ll i = 0; i < h; i++) {
        for (ll j = 0; j < w; j++) {
            if (grid[i][j] != '.' && mark[i][j] == 0) {
                //start a dfs
                mark[i][j] = cnt;
                dfs(i, j);
                cnt++;
            }
        }
    }
    
    set<pair<ll, ll>> edges;
    for (ll i = 0; i < h; i++) {
        for (ll j = 0; j < w; j++) {
            for (ll k = 0; k < 4; k++) {
                ll nr = i + dr[k];
                ll nc = j + dc[k];
                if (nr >= 0 && nr < h && nc >= 0 && nc < w && mark[i][j] != mark[nr][nc]) {
                    edges.insert({mark[i][j], mark[nr][nc]});
                }
            }
        }
    }
    
    vector<ll> adj[cnt];
    for (auto el: edges) {
        adj[el.first].push_back(el.second);
    }
    
    queue<pair<ll, ll>> q;
    q.push({1, 0});
    
    ll dist[cnt];
    for (ll i = 0; i < cnt; i++) {
        dist[i] = INF;
    }
    
    ll ans = 0;
    while (!q.empty()) {
        pair<ll, ll> cur = q.front();
        q.pop();
        
        if (dist[cur.first] != INF) {
            continue;
        }
        
        ans = max(ans, cur.second);
        
        dist[cur.first] = cur.second;
        for (auto el: adj[cur.first]) {
            if (dist[el] == INF) {
                q.push({el, cur.second+1});
            }
        }
    }
    
    cout << ans+1 << endl;
}

int main() {
    mt19937 rng(0);
    // Fast IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  /*
    freopen("piggyback.in", "r", stdin);
    freopen("piggyback.out", "w", stdout);
*/
    ll t = 1;
    //cin >> t;
    
    ll co = 0;
    while (t--) {
        solve(co);
        co++;
    }
}

• Subtask 1: 6.666666666666667 / 30
• Subtask 2: 13.125 / 70