Submission #924004

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924004	2024-02-08T08:34:02 Z	Aiperiii	Tracks in the Snow (BOI13_tracks)	C++14	82.5 / 100	2000 ms	206676 KB

tracks

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=4e3+5;
char a[N][N];
int d[N][N];
int h,w;

signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   cin>>h>>w;
   for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
         cin>>a[i][j];
      }
   }
   vector <int> x={1,-1,0,0},y={0,0,1,-1};
   set <vector <int> > st;
   st.insert({1,0,0});
   d[0][0]=1;
   while(!st.empty()){
      vector <int> v=*st.begin();
      st.erase(st.begin());
      int X=v[1],Y=v[2];
      for(int i=0;i<4;i++){
         if(X+x[i]>=0 && X+x[i]<h && Y+y[i]>=0 && Y+y[i]<w && a[X+x[i]][Y+y[i]]!='.' && d[X+x[i]][Y+y[i]]==0){
            if(a[X+x[i]][Y+y[i]]==a[X][Y])d[X+x[i]][Y+y[i]]=d[X][Y];
            else d[X+x[i]][Y+y[i]]=d[X][Y]+1;
            st.insert({d[X+x[i]][Y+y[i]],X+x[i],Y+y[i]});
         }
      }
   }
   int ans=0;
   for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
         ans=max(ans,d[i][j]);
      }
   }
   cout<<ans<<"\n";
}
 
/*
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
 */

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	9300 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	39 ms	9356 KB	Output is correct
5	Correct	7 ms	4184 KB	Output is correct
6	Correct	1 ms	2392 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Correct	2 ms	2652 KB	Output is correct
9	Correct	1 ms	2904 KB	Output is correct
10	Correct	7 ms	3676 KB	Output is correct
11	Correct	10 ms	4140 KB	Output is correct
12	Correct	21 ms	4688 KB	Output is correct
13	Correct	7 ms	4188 KB	Output is correct
14	Correct	8 ms	4184 KB	Output is correct
15	Correct	45 ms	8536 KB	Output is correct
16	Correct	59 ms	9092 KB	Output is correct
17	Correct	29 ms	8536 KB	Output is correct
18	Correct	43 ms	9384 KB	Output is correct

Subtask #2

52.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	31324 KB	Output is correct
2	Correct	168 ms	19740 KB	Output is correct
3	Correct	854 ms	90132 KB	Output is correct
4	Correct	216 ms	47184 KB	Output is correct
5	Correct	585 ms	71128 KB	Output is correct
6	Execution timed out	2070 ms	194236 KB	Time limit exceeded
7	Correct	11 ms	32600 KB	Output is correct
8	Correct	13 ms	31324 KB	Output is correct
9	Correct	7 ms	2908 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	11 ms	32092 KB	Output is correct
12	Correct	2 ms	3164 KB	Output is correct
13	Correct	164 ms	19796 KB	Output is correct
14	Correct	95 ms	13144 KB	Output is correct
15	Correct	54 ms	19568 KB	Output is correct
16	Correct	82 ms	7944 KB	Output is correct
17	Correct	430 ms	36664 KB	Output is correct
18	Correct	205 ms	51616 KB	Output is correct
19	Correct	219 ms	47188 KB	Output is correct
20	Correct	204 ms	31648 KB	Output is correct
21	Correct	510 ms	64748 KB	Output is correct
22	Correct	581 ms	71136 KB	Output is correct
23	Correct	825 ms	58152 KB	Output is correct
24	Correct	455 ms	63140 KB	Output is correct
25	Correct	952 ms	155812 KB	Output is correct
26	Execution timed out	2058 ms	100492 KB	Time limit exceeded
27	Execution timed out	2094 ms	125408 KB	Time limit exceeded
28	Execution timed out	2078 ms	194000 KB	Time limit exceeded
29	Execution timed out	2011 ms	206676 KB	Time limit exceeded
30	Execution timed out	2033 ms	204980 KB	Time limit exceeded
31	Execution timed out	2066 ms	97800 KB	Time limit exceeded
32	Execution timed out	2017 ms	116572 KB	Time limit exceeded