Submission #875937

#	Time	Username	Problem	Language	Result	Execution time	Memory
875937		431jericho	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	927 ms	174456 KiB

tracks

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <utility>
#include <stack>
#include <math.h>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <numeric>


using namespace std;
#define int long long
#define INF (int)1e18
// #define endl '\n'
const int mod = 1000 * 1000 * 1000 + 7;
const int N = 4005;
#define f first
#define s second

// mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

char a[N][N];
queue<pair<int,int> > pq , nq;
int vis[N][N];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
void Solve() {
    int n , m; cin>>n>>m;
    for(int i = 1 ;i<= n ; i++){
        for(int j = 1; j<= m ; j++){
            cin>>a[i][j];
        }
    }
    int cnt = 0;
    char c ;
    vis[1][1] = true;
    pq.push({1,1});
    while (!pq.empty()){
        cnt++;
        c = a[pq.front().first][pq.front().second];
        while (!pq.empty())nq.push(pq.front()) , pq.pop();
        while (!nq.empty()){
            auto v = nq.front();
            // cout << v.first << " " << v.second << endl;
            nq.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = v.first+dx[i], ny = v.second + dy[i];
                if (nx<1 || ny<1 ||nx>n ||ny>m || a[nx][ny]=='.' || vis[nx][ny]){continue;}
                    vis[nx][ny] = true;
                    // cout << nx << " " << ny << " " << vis[nx][ny] << endl;
                    if (a[nx][ny]==c){
                        nq.push({nx,ny});
                    }
                    else{
                        pq.push({nx,ny});
                    }
                // }
            }
        }
    }
    cout<<cnt<<endl;
}

int32_t main() {
    // auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(0);

// #ifndef ONLINE_JUDGE
//     freopen("in.txt", "r", stdin);
//     freopen("out.txt", "w", stdout);
// #endif

    int t = 1;
 //   cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    // auto end = std::chrono::high_resolution_clock::now();
    // auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

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