oj.uz

Submission #923893

# Submission time Handle Problem Language Result Execution time Memory
923893 2024-02-08T04:59:05 Z Aiperiii Tracks in the Snow (BOI13_tracks) C++14
38.75 / 100
 2000 ms 157636 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 path[N][N];
int h,w;

bool ok(char c){
   vector <int> x={1,-1,0,0};
   vector <int> y={0,0,1,-1};
   queue <pair <int,int> > q;
   q.push({0,0});
   if(a[0][0]==c or a[0][0]=='*'){
      path[0][0]=1;
      while(!q.empty()){
         int X=q.front().ff;
         int Y=q.front().ss;
         q.pop();
         for(int i=0;i<4;i++){
            if(X+x[i]>=0 && X+x[i]<h && Y+y[i]>=0 && Y+y[i]<w){
               if((a[X+x[i]][Y+y[i]]==c or a[X+x[i]][Y+y[i]]=='*') && !path[X+x[i]][Y+y[i]]){
                  path[X+x[i]][Y+y[i]]=1;
                  q.push({X+x[i],Y+y[i]});
               }
            }
         }
      }
   }
   if(path[h-1][w-1]){
      bool fg=0;
      for(int i=0;i<h;i++){
         for(int j=0;j<w;j++){
            if(path[i][j]){
               if(a[i][j]=='R' or a[i][j]=='F')fg=1;
               a[i][j]='*';
            }
            path[i][j]=0;
         }
      }
      if(fg)return true;
      else return false;
   }
   return false;
}
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];
      }
   }
   
   int ans=0;
   while(true){
      int cnt=0;
      for(int i=0;i<h;i++){
         for(int j=0;j<w;j++){
            if(a[i][j]=='.' or a[i][j]=='*')cnt++;
         }
      }
      if(cnt==h*w)break;
      if(ok('F'))ans++;
      else if(ok('R'))ans++;
   }
   cout<<ans<<"\n";
}

/*
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
 */

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 8540 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 24 ms 7660 KB Output is correct
5 Correct 109 ms 4188 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 4 ms 2908 KB Output is correct
10 Correct 103 ms 4044 KB Output is correct
11 Correct 6 ms 3416 KB Output is correct
12 Correct 70 ms 4188 KB Output is correct
13 Correct 105 ms 4184 KB Output is correct
14 Correct 108 ms 4376 KB Output is correct
15 Correct 586 ms 8788 KB Output is correct
16 Correct 231 ms 8624 KB Output is correct
17 Correct 622 ms 8556 KB Output is correct
18 Correct 24 ms 7772 KB Output is correct

Subtask #2
8.75 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 31324 KB Time limit exceeded
2 Execution timed out 2060 ms 25380 KB Time limit exceeded
3 Execution timed out 2070 ms 157268 KB Time limit exceeded
4 Execution timed out 2017 ms 49232 KB Time limit exceeded
5 Execution timed out 2050 ms 103848 KB Time limit exceeded
6 Execution timed out 2070 ms 157628 KB Time limit exceeded
7 Execution timed out 2068 ms 32860 KB Time limit exceeded
8 Execution timed out 2068 ms 31324 KB Time limit exceeded
9 Correct 184 ms 2904 KB Output is correct
10 Correct 492 ms 2652 KB Output is correct
11 Correct 1179 ms 32336 KB Output is correct
12 Execution timed out 2033 ms 3160 KB Time limit exceeded
13 Execution timed out 2062 ms 25428 KB Time limit exceeded
14 Execution timed out 2049 ms 15956 KB Time limit exceeded
15 Execution timed out 2025 ms 19280 KB Time limit exceeded
16 Execution timed out 2027 ms 9720 KB Time limit exceeded
17 Execution timed out 2053 ms 52308 KB Time limit exceeded
18 Execution timed out 2027 ms 51644 KB Time limit exceeded
19 Execution timed out 2054 ms 49236 KB Time limit exceeded
20 Execution timed out 2031 ms 45860 KB Time limit exceeded
21 Execution timed out 2090 ms 109116 KB Time limit exceeded
22 Execution timed out 2066 ms 103992 KB Time limit exceeded
23 Execution timed out 2063 ms 88900 KB Time limit exceeded
24 Execution timed out 2068 ms 107196 KB Time limit exceeded
25 Execution timed out 2059 ms 157060 KB Time limit exceeded
26 Correct 680 ms 136420 KB Output is correct
27 Execution timed out 2067 ms 157636 KB Time limit exceeded
28 Execution timed out 2050 ms 157544 KB Time limit exceeded
29 Execution timed out 2066 ms 157628 KB Time limit exceeded
30 Execution timed out 2068 ms 154372 KB Time limit exceeded
31 Execution timed out 2048 ms 118176 KB Time limit exceeded
32 Execution timed out 2041 ms 157524 KB Time limit exceeded