oj.uz

Submission #821724

# Submission time Handle Problem Language Result Execution time Memory
821724 2023-08-11T13:51:10 Z Metal_Sonic Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 699 ms 137424 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) (x).size()
#define all(x) x.begin() , x.end()
#define F first
#define S second
void Sonic(string name = "") {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if(sz(name)){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}
int xd[] = {0, 1, -1, 0, 1, 1, -1, -1};
int yd[] = {1, 0, 0, -1, 1, -1, 1, -1};
const int mod = 1e9 + 7, MAXN = 1e6 + 5;

void run_test_case(){
    int n,m;cin>>n>>m;
    char grid[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)cin>>grid[i][j];
    }
    vector<vector<int>>dist(n,vector<int>(m,INT_MAX));
    deque<pair<int,int>>dq;
    dist[0][0] = 1;
    dq.push_back({0,0});
    while(!dq.empty()){
        int i = dq.front().first, j = dq.front().second;
        dq.pop_front();
        for(int k = 0; k < 4; k++){
            int ni = i+xd[k], nj = j+yd[k];
            if(ni<0||nj<0||ni>=n||nj>=m||grid[ni][nj]=='.')continue;
            bool f = (grid[i][j] == grid[ni][nj]);
            if(dist[i][j] + !f < dist[ni][nj]){
                if(!f)dq.push_back({ni,nj});
                else dq.push_front({ni,nj});
                dist[ni][nj] = dist[i][j]+!f;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(dist[i][j]==INT_MAX)continue;
            ans = max(ans,dist[i][j]);
        }
    }
    cout<<ans;
}
int main(){
    Sonic();
    int T = 1;
    //cin>>T;
    while(T--){
        run_test_case();
    }
    return 0;
}

Compilation message

tracks.cpp: In function 'void Sonic(std::string)':
tracks.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1748 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 712 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 10 ms 1832 KB Output is correct
16 Correct 10 ms 1816 KB Output is correct
17 Correct 8 ms 1676 KB Output is correct
18 Correct 6 ms 1356 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 41 ms 9516 KB Output is correct
3 Correct 277 ms 94396 KB Output is correct
4 Correct 74 ms 22380 KB Output is correct
5 Correct 190 ms 53248 KB Output is correct
6 Correct 699 ms 108844 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 39 ms 9532 KB Output is correct
14 Correct 23 ms 5660 KB Output is correct
15 Correct 18 ms 6100 KB Output is correct
16 Correct 22 ms 4136 KB Output is correct
17 Correct 103 ms 24100 KB Output is correct
18 Correct 79 ms 23744 KB Output is correct
19 Correct 73 ms 22356 KB Output is correct
20 Correct 62 ms 20556 KB Output is correct
21 Correct 166 ms 55096 KB Output is correct
22 Correct 185 ms 53252 KB Output is correct
23 Correct 207 ms 45772 KB Output is correct
24 Correct 161 ms 53736 KB Output is correct
25 Correct 445 ms 94384 KB Output is correct
26 Correct 659 ms 122444 KB Output is correct
27 Correct 609 ms 137424 KB Output is correct
28 Correct 639 ms 108832 KB Output is correct
29 Correct 653 ms 105900 KB Output is correct
30 Correct 670 ms 112828 KB Output is correct
31 Correct 431 ms 61000 KB Output is correct
32 Correct 579 ms 117372 KB Output is correct