oj.uz

Submission #875937

# Submission time Handle Problem Language Result Execution time Memory
875937 2023-11-20T19:28:14 Z 431jericho Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 927 ms 174456 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8540 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 7 ms 8008 KB Output is correct
5 Correct 3 ms 4184 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2820 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 3 ms 3676 KB Output is correct
11 Correct 2 ms 3676 KB Output is correct
12 Correct 5 ms 4444 KB Output is correct
13 Correct 3 ms 4188 KB Output is correct
14 Correct 3 ms 4188 KB Output is correct
15 Correct 10 ms 8280 KB Output is correct
16 Correct 12 ms 8768 KB Output is correct
17 Correct 9 ms 8284 KB Output is correct
18 Correct 7 ms 8024 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31324 KB Output is correct
2 Correct 44 ms 19804 KB Output is correct
3 Correct 272 ms 88208 KB Output is correct
4 Correct 78 ms 46676 KB Output is correct
5 Correct 182 ms 69972 KB Output is correct
6 Correct 927 ms 174416 KB Output is correct
7 Correct 11 ms 32608 KB Output is correct
8 Correct 12 ms 31576 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 11 ms 32124 KB Output is correct
12 Correct 1 ms 3164 KB Output is correct
13 Correct 50 ms 19736 KB Output is correct
14 Correct 27 ms 13148 KB Output is correct
15 Correct 24 ms 19404 KB Output is correct
16 Correct 20 ms 7720 KB Output is correct
17 Correct 124 ms 35908 KB Output is correct
18 Correct 107 ms 51248 KB Output is correct
19 Correct 95 ms 46672 KB Output is correct
20 Correct 64 ms 31568 KB Output is correct
21 Correct 160 ms 63316 KB Output is correct
22 Correct 182 ms 69952 KB Output is correct
23 Correct 242 ms 56660 KB Output is correct
24 Correct 154 ms 61768 KB Output is correct
25 Correct 574 ms 153892 KB Output is correct
26 Correct 447 ms 133780 KB Output is correct
27 Correct 602 ms 157280 KB Output is correct
28 Correct 887 ms 174456 KB Output is correct
29 Correct 897 ms 171416 KB Output is correct
30 Correct 759 ms 166648 KB Output is correct
31 Correct 577 ms 116464 KB Output is correct
32 Correct 588 ms 155460 KB Output is correct