oj.uz

Submission #438940

# Submission time Handle Problem Language Result Execution time Memory
438940 2021-06-29T00:57:52 Z dawangk Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1022 ms 130544 KB 
#include <bits/stdc++.h>
using namespace std;
#define inputJunk ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug cout<<"HERE"<<endl;
#define ell "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<pi, int> trip;
typedef pair<pll, ll> tripll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<trip> vtrip;

const int INF = 1e9+1212;
const ll P = 9973, M = 1e9+9;
const int MM = 4e3+5; int mod = 1e9+7;//998244353

int w, h; char grid [MM][MM];
int ans = 0;
pi dir[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int dist[MM][MM];

bool valid(int x, int y){
    return x>=0&&x<w&&y>=0&&y<h&&grid[x][y]!='.'&&dist[x][y]==0;
}


int main(){
    inputJunk
    cin>>w>>h;
    for(int i= 0;i<w;i++){
        cin>>grid[i];
    }

    deque<pi> q;
    q.push_front({0, 0});
    dist[0][0] = 1;
    while(!q.empty()){
        int curx = q.front().f, cury = q.front().s;
        q.pop_front();

        for(int i = 0;i<4;i++){
            int newx = curx+dir[i].f, newy = cury+dir[i].s;

            if(valid(newx, newy)){
                if(grid[newx][newy]==grid[curx][cury]){
                    dist[newx][newy] = dist[curx][cury];
                    ans = max(ans, dist[newx][newy]);
                    q.push_front({newx, newy});
                }else{
                    dist[newx][newy] = dist[curx][cury]+1;
                    ans = max(ans, dist[newx][newy]);
                    q.push_back({newx, newy});
                }
            }
        }

    }

    cout<<ans<<ell;

}
/*CUSTOM TEST CASE 1
*/

/*CUSTOM TEST CASE 2
*/

/*CUSTOM TEST CASE 3
*/

/*Comments of Shame
- floating error (use integer division instead)
- cin vs getline
- upperbound and lowerbound returns iterators
- use long long when number is big enough
- for dp invalid cases needs to be skipped
- some base cases won't work (review cow poetry)
- always check bounds, some TLE are due to incorrect bounds!
- dont mess up return types
= RESET ARRAYS!!!!!!!!!!
- USE UR BRAIN
*/
/*
    freopen("time.in","r", stdin);
    freopen("time.out","w", stdout);
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5320 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 13 ms 5116 KB Output is correct
5 Correct 4 ms 2892 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 716 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 3 ms 2380 KB Output is correct
11 Correct 3 ms 2124 KB Output is correct
12 Correct 9 ms 3048 KB Output is correct
13 Correct 4 ms 2892 KB Output is correct
14 Correct 4 ms 2892 KB Output is correct
15 Correct 17 ms 5244 KB Output is correct
16 Correct 18 ms 5320 KB Output is correct
17 Correct 11 ms 5196 KB Output is correct
18 Correct 10 ms 5068 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 30820 KB Output is correct
2 Correct 48 ms 15116 KB Output is correct
3 Correct 204 ms 72588 KB Output is correct
4 Correct 100 ms 32596 KB Output is correct
5 Correct 152 ms 53384 KB Output is correct
6 Correct 816 ms 106336 KB Output is correct
7 Correct 23 ms 32196 KB Output is correct
8 Correct 21 ms 30760 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 22 ms 31620 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 47 ms 15040 KB Output is correct
14 Correct 28 ms 10316 KB Output is correct
15 Correct 36 ms 13048 KB Output is correct
16 Correct 20 ms 5612 KB Output is correct
17 Correct 118 ms 28724 KB Output is correct
18 Correct 103 ms 35624 KB Output is correct
19 Correct 82 ms 32616 KB Output is correct
20 Correct 54 ms 25516 KB Output is correct
21 Correct 132 ms 52416 KB Output is correct
22 Correct 148 ms 53364 KB Output is correct
23 Correct 231 ms 43732 KB Output is correct
24 Correct 133 ms 49760 KB Output is correct
25 Correct 539 ms 92568 KB Output is correct
26 Correct 1022 ms 130544 KB Output is correct
27 Correct 844 ms 110572 KB Output is correct
28 Correct 829 ms 105460 KB Output is correct
29 Correct 814 ms 103224 KB Output is correct
30 Correct 830 ms 107972 KB Output is correct
31 Correct 622 ms 73008 KB Output is correct
32 Correct 872 ms 108340 KB Output is correct