oj.uz

답안 #924004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924004 2024-02-08T08:34:02 Z Aiperiii Tracks in the Snow (BOI13_tracks) C++14
82.5 / 100
 2000 ms 206676 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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