oj.uz

Submission #158969

# Submission time Handle Problem Language Result Execution time Memory
158969 2019-10-19T17:09:06 Z Kerim Tracks in the Snow (BOI13_tracks) C++17
8.33333 / 100
 245 ms 10876 KB 
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,m;
const int N=1e3+5;
char arr[N][N];
int dx[]={+1,-1,0,0};
int dy[]={0,0,+1,-1};
int vis[N][N];
int relax(queue<PII>q){
    if(q.empty())
        return 0;
    queue<PII>wow;
    while(!q.empty()){
        PII nd=q.front();q.pop();
    //    cout<<nd.ff<<" "<<nd.ss<<endl;
        for(int i=0;i<4;i++){
            int nx=nd.ff+dx[i];
            int ny=nd.ss+dy[i];
            if(nx>=1 and ny>=1 and nx<=n and ny<=m and !vis[nx][ny] and arr[nx][ny]==arr[nd.ff][nd.ss]){
                vis[nx][ny]=1;
                for(int j=0;j<4;j++){
                    int tox=nx+dx[j];
                    int toy=ny+dy[j];        
                    if(tox>=1 and toy>=1 and tox<=n and toy<=m and !vis[tox][toy] and arr[nx][ny]!=arr[tox][toy] and arr[tox][toy]!='*'){
                        wow.push(mp(tox,toy));
                        vis[tox][toy]=1;    
                    }
                }
                q.push(mp(nx,ny));    
            }
        }
    }
    return relax(wow)+1;
}
int main(){
   // freopen("file.in", "r", stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf(" %c",&arr[i][j]);
    vis[1][1]=1;queue<PII>uf;uf.push(mp(1,1));
    printf("%d\n",relax(uf));
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:57:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&arr[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
8.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3960 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 632 KB Output isn't correct
4 Correct 22 ms 3164 KB Output is correct
5 Incorrect 13 ms 2040 KB Output isn't correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Incorrect 2 ms 632 KB Output isn't correct
8 Incorrect 3 ms 632 KB Output isn't correct
9 Incorrect 4 ms 888 KB Output isn't correct
10 Incorrect 10 ms 1912 KB Output isn't correct
11 Correct 7 ms 1400 KB Output is correct
12 Incorrect 14 ms 2140 KB Output isn't correct
13 Incorrect 13 ms 2040 KB Output isn't correct
14 Incorrect 13 ms 2040 KB Output isn't correct
15 Incorrect 34 ms 4088 KB Output isn't correct
16 Correct 37 ms 4028 KB Output is correct
17 Incorrect 35 ms 3704 KB Output isn't correct
18 Correct 39 ms 3164 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5 ms 1400 KB Time limit exceeded (wall clock)
2 Execution timed out 76 ms 2808 KB Time limit exceeded (wall clock)
3 Execution timed out 237 ms 5496 KB Time limit exceeded (wall clock)
4 Execution timed out 123 ms 3448 KB Time limit exceeded (wall clock)
5 Execution timed out 179 ms 4528 KB Time limit exceeded (wall clock)
6 Execution timed out 237 ms 5400 KB Time limit exceeded (wall clock)
7 Execution timed out 5 ms 1400 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 1400 KB Time limit exceeded (wall clock)
9 Incorrect 6 ms 504 KB Output isn't correct
10 Incorrect 4 ms 632 KB Output isn't correct
11 Execution timed out 4 ms 1400 KB Time limit exceeded (wall clock)
12 Incorrect 5 ms 1272 KB Output isn't correct
13 Execution timed out 76 ms 2680 KB Time limit exceeded (wall clock)
14 Incorrect 111 ms 9992 KB Output isn't correct
15 Incorrect 107 ms 10876 KB Output isn't correct
16 Incorrect 62 ms 4600 KB Output isn't correct
17 Execution timed out 120 ms 3420 KB Time limit exceeded (wall clock)
18 Execution timed out 120 ms 3448 KB Time limit exceeded (wall clock)
19 Execution timed out 120 ms 3448 KB Time limit exceeded (wall clock)
20 Execution timed out 118 ms 3452 KB Time limit exceeded (wall clock)
21 Execution timed out 178 ms 4572 KB Time limit exceeded (wall clock)
22 Execution timed out 178 ms 4432 KB Time limit exceeded (wall clock)
23 Execution timed out 184 ms 4524 KB Time limit exceeded (wall clock)
24 Execution timed out 175 ms 4348 KB Time limit exceeded (wall clock)
25 Execution timed out 237 ms 5404 KB Time limit exceeded (wall clock)
26 Execution timed out 208 ms 4856 KB Time limit exceeded (wall clock)
27 Execution timed out 236 ms 5240 KB Time limit exceeded (wall clock)
28 Execution timed out 245 ms 5448 KB Time limit exceeded (wall clock)
29 Execution timed out 237 ms 5500 KB Time limit exceeded (wall clock)
30 Execution timed out 237 ms 5368 KB Time limit exceeded (wall clock)
31 Execution timed out 196 ms 4592 KB Time limit exceeded (wall clock)
32 Execution timed out 237 ms 5480 KB Time limit exceeded (wall clock)