oj.uz

Submission #371124

# Submission time Handle Problem Language Result Execution time Memory
371124 2021-02-25T21:43:41 Z plourde27 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1625 ms 307188 KB 
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <fstream>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <list>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef map<int, int> mii;
typedef map<int, string> mis;
typedef map<string, int> msi;
typedef set<int> si;
typedef set<ll> sl;
typedef map<ll, ll> mll;
typedef queue<int> qi;
typedef queue<ii> qii;
typedef vector<string> vs;
typedef pair<ll, ll> iil;
typedef priority_queue<int> pqi;
typedef priority_queue<ii> pqii;
typedef priority_queue<ll> pqil;
typedef priority_queue<iil> pqiil;
typedef vector<iil> viil;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int, ii> iii;
typedef pair<iil, ll> iiil;
typedef vector<pair<pair<int,int>,int> > viii;
typedef vector<pair<pair<ll,ll>,ll> > viiil;
typedef vector<vl> vvl;

#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0 ; i < n ; i++)
#define rrep(i, m, n) for (int i = m ; i < n ; i++)
#define per(i, n) for (int i = n - 1 ; i >= 0 ; i--)
#define perr(i, m, n) for (int i = n - 1 ; i >= m ; i--)
#define INF 2000000000

ll MOD = 1000000007;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int vis[4005][4005];
int dist[4005][4005];

void solve() {
    int n, m;
    cin >> n >> m;
    
    int mat[n][m];
    
    rep(i, n) {
        string s;
        cin >> s;
        rep(j, m) {
            mat[i][j] = s[j];
        }
    }
    
    deque<pair<pair<int, int>, int>> q;
    
    q.push_back({{0, 0}, 0});
    
    rep(i, n) {
        rep(j, m) {
            dist[i][j] = INF;
        }
    }
    
    while (q.size()) {
        pair<pair<int, int>, int> inf = q.front();
        q.pop_front();
        
        int x = inf.first.first;
        int y = inf.first.second;
        int d = inf.second;
        
        dist[x][y] = min(dist[x][y], d);
        
        
        vis[x][y] = true;
        
        rep(k, 4) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
            if (mat[xx][yy] == '.') continue;
            
            if (mat[xx][yy] == mat[x][y]) {
                if (d < dist[xx][yy]) {
                    q.push_front({{xx, yy}, d});
                }
            }
            else {
                if (d+1 < dist[xx][yy]) {
                    q.push_back({{xx, yy}, d+1});
                }
            }
        }
        
        
    }
    
    int ans = 0;
    
    rep(i, n) {
        rep(j, m) {
            if (dist[i][j] != INF) {
                //cout << dist[i][j] << " ";
                ans = max(ans, dist[i][j]);
            }
            else {
                //cout << 0 << " ";
            }
        }
        //cout << endl;
    }
    
    cout << ans+1 << endl;
}

void querySolve() {
    int t;
    cin >> t;
    for (int i = 0 ; i < t ; i++) {
        solve();
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    solve();
    //querySolve();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7532 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 17 ms 6892 KB Output is correct
5 Correct 5 ms 3840 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 1260 KB Output is correct
10 Correct 5 ms 3052 KB Output is correct
11 Correct 5 ms 2668 KB Output is correct
12 Correct 13 ms 3948 KB Output is correct
13 Correct 5 ms 3692 KB Output is correct
14 Correct 5 ms 3692 KB Output is correct
15 Correct 28 ms 7532 KB Output is correct
16 Correct 37 ms 7532 KB Output is correct
17 Correct 18 ms 7148 KB Output is correct
18 Correct 17 ms 6892 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31724 KB Output is correct
2 Correct 96 ms 26988 KB Output is correct
3 Correct 395 ms 169040 KB Output is correct
4 Correct 119 ms 59388 KB Output is correct
5 Correct 213 ms 115820 KB Output is correct
6 Correct 1542 ms 237900 KB Output is correct
7 Correct 20 ms 33132 KB Output is correct
8 Correct 18 ms 31724 KB Output is correct
9 Correct 4 ms 1132 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 18 ms 32492 KB Output is correct
12 Correct 2 ms 1900 KB Output is correct
13 Correct 93 ms 27244 KB Output is correct
14 Correct 54 ms 17644 KB Output is correct
15 Correct 36 ms 21100 KB Output is correct
16 Correct 48 ms 10860 KB Output is correct
17 Correct 230 ms 57964 KB Output is correct
18 Correct 135 ms 64492 KB Output is correct
19 Correct 122 ms 59756 KB Output is correct
20 Correct 102 ms 50668 KB Output is correct
21 Correct 243 ms 117484 KB Output is correct
22 Correct 213 ms 116076 KB Output is correct
23 Correct 446 ms 96876 KB Output is correct
24 Correct 177 ms 113260 KB Output is correct
25 Correct 664 ms 190104 KB Output is correct
26 Correct 834 ms 307188 KB Output is correct
27 Correct 1172 ms 269948 KB Output is correct
28 Correct 1555 ms 238776 KB Output is correct
29 Correct 1522 ms 231364 KB Output is correct
30 Correct 1377 ms 252536 KB Output is correct
31 Correct 1625 ms 143068 KB Output is correct
32 Correct 1008 ms 258928 KB Output is correct