oj.uz

Submission #955346

# Submission time Handle Problem Language Result Execution time Memory
955346 2024-03-30T07:48:25 Z doducanh Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 851 ms 148208 KB 
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
int dx[4]={0,1,-1,0};
int dy[4]={-1,0,0,1};
const int maxn=4005;
string s[maxn];
int d[maxn][maxn];
int n,m;
bool check(int x,int y)
{
    return ((x>-1)&&(x<n)&&(y>-1)&&(y<m)&&(s[x][y]!='.')&&(d[x][y]==0));
}
main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>s[i];
    d[0][0]=1;
    deque<ii>dq;
    int ans=0;
    dq.push_back({0,0});
    while(dq.size()){
        ii c=dq.front();
        dq.pop_front();
        ans=max(ans,d[c.fi][c.se]);
        for(int i=0;i<4;i++){
            int x=c.fi+dx[i];
            int y=c.se+dy[i];
            if(check(x,y)){
                if(s[c.fi][c.se]!=s[x][y]){
                    d[x][y]=d[c.fi][c.se]+1;
                    dq.push_back({x,y});
                }
                else{
                    d[x][y]=d[c.fi][c.se];
                    dq.push_front({x,y});
                }
            }
        }
    }
    cout<<ans;
}

Compilation message

tracks.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main()
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4184 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 10 ms 3660 KB Output is correct
5 Correct 3 ms 2148 KB Output is correct
6 Correct 1 ms 608 KB Output is correct
7 Correct 1 ms 616 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 864 KB Output is correct
10 Correct 3 ms 1892 KB Output is correct
11 Correct 2 ms 1636 KB Output is correct
12 Correct 6 ms 2236 KB Output is correct
13 Correct 5 ms 2152 KB Output is correct
14 Correct 3 ms 2152 KB Output is correct
15 Correct 11 ms 3944 KB Output is correct
16 Correct 13 ms 4092 KB Output is correct
17 Correct 10 ms 3944 KB Output is correct
18 Correct 8 ms 3688 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15976 KB Output is correct
2 Correct 54 ms 12592 KB Output is correct
3 Correct 352 ms 88144 KB Output is correct
4 Correct 97 ms 32536 KB Output is correct
5 Correct 243 ms 53172 KB Output is correct
6 Correct 851 ms 123772 KB Output is correct
7 Correct 9 ms 16736 KB Output is correct
8 Correct 9 ms 15976 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 9 ms 16488 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct
13 Correct 61 ms 12624 KB Output is correct
14 Correct 29 ms 8796 KB Output is correct
15 Correct 30 ms 11244 KB Output is correct
16 Correct 23 ms 4952 KB Output is correct
17 Correct 141 ms 28724 KB Output is correct
18 Correct 114 ms 35640 KB Output is correct
19 Correct 105 ms 32596 KB Output is correct
20 Correct 91 ms 25424 KB Output is correct
21 Correct 229 ms 52228 KB Output is correct
22 Correct 237 ms 53072 KB Output is correct
23 Correct 249 ms 43528 KB Output is correct
24 Correct 212 ms 49616 KB Output is correct
25 Correct 555 ms 108880 KB Output is correct
26 Correct 772 ms 130652 KB Output is correct
27 Correct 711 ms 148208 KB Output is correct
28 Correct 766 ms 123824 KB Output is correct
29 Correct 748 ms 122144 KB Output is correct
30 Correct 734 ms 126168 KB Output is correct
31 Correct 504 ms 73120 KB Output is correct
32 Correct 693 ms 129380 KB Output is correct