oj.uz

Submission #861305

# Submission time Handle Problem Language Result Execution time Memory
861305 2023-10-16T01:22:39 Z nnhzzz Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 578 ms 137648 KB 
#include<bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i += c)
#define task "test"
#define task1 "nnhzzz"
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define MASK(x) (1LL<<x)
#define BIT(x,i) ((x>>i)&1LL)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define fi first
#define se second
#define ld long double
#define ll long long

//-------------------------------------------------------------------------------//
template<typename T> bool mini(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, T b){if(a<b){a=b;return true;}return false;}
//-------------------------------------------------------------------------------//
const int MAXN = 4e3+7,N = 1e5+7,inf = 1e9,LOG = 20;
const int MOD = 1e9+7,MOD1 = 123456789;
const int dx[] = {1,0,0,-1};
const int dy[] = {0,1,-1,0};
//-------------------------------------------------------------------------------//

char c[MAXN][MAXN];
int d[MAXN][MAXN];
int n,m,res = 0;

bool ok(int x, int y){
    return (x>=1 && y>=1 && x<=n && y<=m);
}

void solve(){
    cin >> n >> m;
    REP(i,1,n) REP(j,1,m) cin >> c[i][j];
    deque<pii> q; d[1][1] = 1;
    q.emplace_back(1,1);
    while(SZ(q)!=0){
        int x = q.front().fi,y = q.front().se; q.pop_front();
        REP(i,0,3){
            int nx = x+dx[i],ny = y+dy[i];
            if(ok(nx,ny)==false || c[nx][ny]=='.' || d[nx][ny]!=0) continue;
            if(c[x][y]==c[nx][ny]){
                d[nx][ny] = d[x][y];
                q.emplace_front(nx,ny);
            }else{
                maxi(res,d[x][y]+1);
                d[nx][ny] = d[x][y]+1;
                q.emplace_back(nx,ny);
            }
        }
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    if(fopen(task1".inp","r")){
        freopen(task1".inp","r",stdin);
        freopen(task1".out","w",stdout);
    }
    solve();
    return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7612 KB Output is correct
2 Correct 2 ms 2604 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 6 ms 7272 KB Output is correct
5 Correct 3 ms 5980 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 2652 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 3 ms 5724 KB Output is correct
11 Correct 2 ms 3672 KB Output is correct
12 Correct 5 ms 5980 KB Output is correct
13 Correct 4 ms 5928 KB Output is correct
14 Correct 3 ms 5980 KB Output is correct
15 Correct 9 ms 7388 KB Output is correct
16 Correct 10 ms 7696 KB Output is correct
17 Correct 9 ms 7516 KB Output is correct
18 Correct 6 ms 7272 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 32444 KB Output is correct
2 Correct 38 ms 16212 KB Output is correct
3 Correct 322 ms 73772 KB Output is correct
4 Correct 68 ms 35668 KB Output is correct
5 Correct 153 ms 56108 KB Output is correct
6 Correct 551 ms 108988 KB Output is correct
7 Correct 10 ms 33120 KB Output is correct
8 Correct 10 ms 32312 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 10 ms 32860 KB Output is correct
12 Correct 2 ms 3160 KB Output is correct
13 Correct 36 ms 16320 KB Output is correct
14 Correct 23 ms 13144 KB Output is correct
15 Correct 23 ms 15264 KB Output is correct
16 Correct 18 ms 8428 KB Output is correct
17 Correct 92 ms 31124 KB Output is correct
18 Correct 74 ms 38224 KB Output is correct
19 Correct 69 ms 35688 KB Output is correct
20 Correct 61 ms 26940 KB Output is correct
21 Correct 152 ms 54968 KB Output is correct
22 Correct 157 ms 55992 KB Output is correct
23 Correct 185 ms 46160 KB Output is correct
24 Correct 145 ms 52024 KB Output is correct
25 Correct 375 ms 94372 KB Output is correct
26 Incorrect 334 ms 133896 KB Output isn't correct
27 Correct 454 ms 137648 KB Output is correct
28 Correct 545 ms 109032 KB Output is correct
29 Correct 578 ms 106684 KB Output is correct
30 Correct 492 ms 113316 KB Output is correct
31 Correct 397 ms 75456 KB Output is correct
32 Correct 447 ms 116200 KB Output is correct