Submission #997678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
997678	2024-06-12T17:03:34 Z	Mil0S	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	566 ms	125060 KB

tracks

#include <bits/stdc++.h>
using namespace std;
int n,m;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int mini=0;
char polja[4001][4001];

bool check(int x, int y){
if(x<0)return 0;
if(x>=n)return 0;
if(y<0)return 0;
if(y>=m)return 0;
if(polja[x][y]=='.') return 0;
return 1;
}

void bfs01(){
vector<vector<int>> depth(n+1,vector<int>(m+1,INT_MAX));
deque<pair<int,int>> dq;
depth[0][0]=1;
dq.push_back({0,0});
while(!dq.empty()){
    pair<int,int> u=dq.front();
    dq.pop_front();
    int i=u.first;
    int j=u.second;
    mini=max(mini,depth[i][j]); // maximalan depth
    for(int k=0;k<4;++k){
        int x=i+dx[k];
        int y=j+dy[k];
        if(check(x,y)){
            int c=(polja[x][y]==polja[i][j])?0:1;
            if(depth[x][y]>depth[i][j]+c){
                depth[x][y]=depth[i][j]+c; //relaxing
                if(c==0){
                    dq.push_front({x,y});
                }
                else{
                    dq.push_back({x,y});
                }
            }
        }
    }
}
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;++i){
    for(int j=0;j<m;++j){
        cin>>polja[i][j];
    }
}
bfs01();
cout<<mini;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	3928 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	5 ms	3676 KB	Output is correct
5	Correct	2 ms	2908 KB	Output is correct
6	Correct	0 ms	348 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	2652 KB	Output is correct
10	Correct	2 ms	2908 KB	Output is correct
11	Correct	2 ms	2908 KB	Output is correct
12	Correct	4 ms	3036 KB	Output is correct
13	Correct	2 ms	3032 KB	Output is correct
14	Correct	2 ms	2908 KB	Output is correct
15	Correct	8 ms	3952 KB	Output is correct
16	Correct	11 ms	3932 KB	Output is correct
17	Correct	7 ms	3676 KB	Output is correct
18	Correct	5 ms	3676 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	15708 KB	Output is correct
2	Correct	35 ms	14528 KB	Output is correct
3	Correct	243 ms	94548 KB	Output is correct
4	Correct	74 ms	27248 KB	Output is correct
5	Correct	176 ms	56916 KB	Output is correct
6	Correct	566 ms	108168 KB	Output is correct
7	Correct	3 ms	16476 KB	Output is correct
8	Correct	3 ms	15708 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	2 ms	15964 KB	Output is correct
12	Correct	1 ms	2652 KB	Output is correct
13	Correct	35 ms	14320 KB	Output is correct
14	Correct	20 ms	9052 KB	Output is correct
15	Correct	21 ms	9564 KB	Output is correct
16	Correct	16 ms	5860 KB	Output is correct
17	Correct	92 ms	28784 KB	Output is correct
18	Correct	65 ms	28244 KB	Output is correct
19	Correct	62 ms	27220 KB	Output is correct
20	Correct	55 ms	25680 KB	Output is correct
21	Correct	142 ms	58612 KB	Output is correct
22	Correct	188 ms	57080 KB	Output is correct
23	Correct	192 ms	48720 KB	Output is correct
24	Correct	144 ms	57428 KB	Output is correct
25	Correct	293 ms	94452 KB	Output is correct
26	Correct	315 ms	125060 KB	Output is correct
27	Correct	424 ms	121092 KB	Output is correct
28	Correct	543 ms	108012 KB	Output is correct
29	Correct	552 ms	106692 KB	Output is correct
30	Correct	503 ms	110468 KB	Output is correct
31	Correct	406 ms	65616 KB	Output is correct
32	Correct	410 ms	110092 KB	Output is correct