oj.uz

Submission #467764

# Submission time Handle Problem Language Result Execution time Memory
467764 2021-08-24T11:51:26 Z Yuisuyuno Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 939 ms 234348 KB 
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 4005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

char a[N][N];
int n, m;

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        //freopen(Task".out","w",stdout);
    }
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
        }
    }
}

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

bool ok(int x, int y){
    if (x < 1 || x > n || y < 1 || y > m) return false;
    return true;
}

void proc()
{
    deque<ii> q;
    d[1][1] = 1;
    int ans = 1;
    q.push_front(ii(1,1));
    while (q.size()){
        int u = q.front().fi;
        int v = q.front().se;
        q.pop_front();
        for(int i=0; i<4; i++){
            int nu = u + dx[i];
            int nv = v + dy[i];
            if (ok(nu,nv) && a[nu][nv]!='.' && d[nu][nv]==0){
                if (a[nu][nv]!=a[u][v]){
                    d[nu][nv] = d[u][v]+1;
                    q.pb(ii(nu,nv));
                    ans = max(ans,d[nu][nv]);
                }
                else{
                    q.push_front(ii(nu,nv));
                    d[nu][nv] = d[u][v];
                    ans = max(ans,d[nu][nv]);
                }
            }
        }
    }
    cout << ans;
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message

tracks.cpp: In function 'void readfile()':
tracks.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6208 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 11 ms 5836 KB Output is correct
5 Correct 4 ms 3148 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 4 ms 2508 KB Output is correct
11 Correct 3 ms 2252 KB Output is correct
12 Correct 7 ms 3276 KB Output is correct
13 Correct 4 ms 3148 KB Output is correct
14 Correct 4 ms 3148 KB Output is correct
15 Correct 15 ms 5800 KB Output is correct
16 Correct 17 ms 6152 KB Output is correct
17 Correct 14 ms 5836 KB Output is correct
18 Correct 11 ms 5784 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30924 KB Output is correct
2 Correct 64 ms 17524 KB Output is correct
3 Correct 418 ms 89112 KB Output is correct
4 Correct 129 ms 45252 KB Output is correct
5 Correct 257 ms 69468 KB Output is correct
6 Correct 921 ms 181868 KB Output is correct
7 Correct 20 ms 32460 KB Output is correct
8 Correct 19 ms 30976 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 18 ms 31820 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 65 ms 17552 KB Output is correct
14 Correct 39 ms 11764 KB Output is correct
15 Correct 40 ms 16324 KB Output is correct
16 Correct 29 ms 6652 KB Output is correct
17 Correct 164 ms 35148 KB Output is correct
18 Correct 154 ms 50152 KB Output is correct
19 Correct 132 ms 45384 KB Output is correct
20 Correct 102 ms 29312 KB Output is correct
21 Correct 256 ms 61536 KB Output is correct
22 Correct 258 ms 69572 KB Output is correct
23 Correct 307 ms 55696 KB Output is correct
24 Correct 245 ms 60096 KB Output is correct
25 Correct 748 ms 154968 KB Output is correct
26 Correct 639 ms 234348 KB Output is correct
27 Correct 813 ms 208472 KB Output is correct
28 Correct 939 ms 182432 KB Output is correct
29 Correct 931 ms 179228 KB Output is correct
30 Correct 869 ms 188052 KB Output is correct
31 Correct 691 ms 115348 KB Output is correct
32 Correct 731 ms 180560 KB Output is correct