Submission #1272796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272796		TrinhKhanhDung	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	763 ms	108700 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(), v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define INF (ll)1e9
#define oo (ll)1e18
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

void print(vector<pair<int, int>> v){
    for(auto x: v) cout << x.first << ' ' << x.second << '\n';
}

int fastPow(int a, int n){
    int ans = 1;
    while(n){
        if(n & 1) ans = 1LL * ans * a % MOD;
        a = 1LL * a * a % MOD;
        n >>= 1;
    }
    return ans;
}

ll solve(){
    int n, m; cin >> n >> m;
    vector<vector<char>> a(n + 3, vector<char>(m + 3));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++) cin >> a[i][j];
    }
    vector<vector<int>> mark(n + 3, vector<int>(m + 3, false));
    stack<pair<int, int>> Old, New;
    Old.push({1, 1});
    int ans = 0;
    while((int)Old.size()){
        ans++;
        while((int)Old.size()){
            auto [sx, sy] = Old.top();
            Old.pop();
            if(mark[sx][sy]) continue;
            queue<pair<int, int>> q;
            q.push({sx, sy});
            mark[sx][sy] = true;
            while((int)q.size()){
                auto [x, y] = q.front();
                q.pop();
                int dx[] = {0, 0, 1, -1};
                int dy[] = {1, -1, 0, 0};
                for(int k = 0; k < 4; k++){
                    int nx = x + dx[k], ny = y + dy[k];
                    if(nx < 1 || ny < 1 || nx > n || ny > m || mark[nx][ny] || a[nx][ny] == '.') continue;
                    if(a[nx][ny] != a[x][y]){
                        New.push({nx, ny});
                        continue;
                    }
                    mark[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        Old = New;
        while((int)New.size()) New.pop();
    }
    cout << ans << '\n';
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
//        cout << solve() << '\n';
    }

    return 0;
}

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