oj.uz

Submission #1108793

# Submission time Handle Problem Language Result Execution time Memory
1108793 2024-11-05T06:22:59 Z monaxia Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1000 ms 176784 KB 
// credit: bieoiibe
 
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
#define vektor vector
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;

const ll Mod = 1e9 + 7;

void solve(){
    int n, m, ans = 0;
    cin >> n >> m;

    vector <vector <char>> a(n + 1, vector <char> (m + 1));
    vector <vector <int>> v(n + 1, vector <int> (m + 1, 0)), val(n + 1, vector <int> (m + 1, 0));
    int col[4] = {0, 1, 0, -1}, 
        row[4] = {1, 0, -1, 0};

    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) cin >> a[i][j];
    }

    queue <pair <int, int>> q, w;

    q.push({1, 1});

    v[1][1] = val[1][1] = 1;

    while(!q.empty()){
        int x1 = q.front().fr, y1 = q.front().sc;
        q.pop();

        for(int i = 0; i < 4; i ++){
            int x = x1 + col[i], y = y1 + row[i];
            if(x > n || x < 1 || y > m || y < 1 || a[x][y] == '.' || v[x][y]) continue;

            val[x][y] = val[x1][y1];

            if(a[x][y] != a[x1][y1]) val[x][y] ++, w.push({x, y});
            else v[x][y] = 1, q.push({x, y});
        }

        if(q.empty()){
            // cout << w.size() << "\n";
            while(!q.empty() && v[w.front().fr][w.front().sc]) w.pop();
            if(w.empty()) break;

            v[w.front().fr][w.front().sc] = 1;
            q.push(w.front());
            w.pop();
        }
    }

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) ans = max(ans, val[i][j]);

    cout << ans;
} 

 
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
 
    if(fopen("blank.inp", "r")){
        freopen("blank.inp", "r", stdin);
        freopen("blank.out", "w", stdout);
    }
    
    // cout << 1; return 0;
 
    ll n = 1;
 
    // cin >> n;

    while(n) {
        solve();
        n --;
        cout << "\n";
    }
 
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen("blank.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen("blank.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2896 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 10 ms 2244 KB Output is correct
5 Correct 4 ms 1104 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 4 ms 1104 KB Output is correct
11 Correct 3 ms 848 KB Output is correct
12 Correct 8 ms 1400 KB Output is correct
13 Correct 4 ms 1104 KB Output is correct
14 Correct 4 ms 1104 KB Output is correct
15 Correct 21 ms 2896 KB Output is correct
16 Correct 20 ms 3152 KB Output is correct
17 Correct 13 ms 2896 KB Output is correct
18 Correct 8 ms 2264 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1360 KB Output is correct
2 Correct 65 ms 15956 KB Output is correct
3 Correct 433 ms 157372 KB Output is correct
4 Correct 134 ms 37192 KB Output is correct
5 Correct 255 ms 88920 KB Output is correct
6 Correct 998 ms 176716 KB Output is correct
7 Correct 3 ms 1360 KB Output is correct
8 Correct 3 ms 1360 KB Output is correct
9 Correct 3 ms 1104 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 3 ms 1360 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 67 ms 15952 KB Output is correct
14 Correct 51 ms 9296 KB Output is correct
15 Correct 26 ms 10260 KB Output is correct
16 Correct 33 ms 6820 KB Output is correct
17 Correct 180 ms 40408 KB Output is correct
18 Correct 110 ms 39636 KB Output is correct
19 Correct 107 ms 36644 KB Output is correct
20 Correct 102 ms 34248 KB Output is correct
21 Correct 254 ms 91816 KB Output is correct
22 Correct 231 ms 88904 KB Output is correct
23 Correct 349 ms 76616 KB Output is correct
24 Correct 207 ms 89672 KB Output is correct
25 Correct 445 ms 157512 KB Output is correct
26 Correct 510 ms 120540 KB Output is correct
27 Correct 702 ms 159420 KB Output is correct
28 Correct 1000 ms 176784 KB Output is correct
29 Correct 940 ms 176484 KB Output is correct
30 Correct 835 ms 170236 KB Output is correct
31 Correct 910 ms 102240 KB Output is correct
32 Correct 620 ms 159392 KB Output is correct