oj.uz

Submission #58746

# Submission time Handle Problem Language Result Execution time Memory
58746 2018-07-19T07:23:53 Z Batrr Tracks in the Snow (BOI13_tracks) C++14
93.4375 / 100
 2000 ms 264100 KB 
#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
*/
#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define IOS ios_base::sync_with_stdio(0);

using namespace std;                    

const ll maxn=2e5+123,inf=1e18,mod=1e9+7,N=1e7+12,LOG=20;

int n,m,ans;
pair<int,int> dir[]={{0,-1},{-1,0},{1,0},{0,1}};
bool was[4001][4001];
string s[4001];
bool check(int x,int y){
    if(x<0 || x>=n || y<0 || y>=m || s[x][y]=='.')
        return 0;
     return 1;
}
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>s[i];
    queue< pair<int,int> > q1,q2;
    q1.push({0,0});
    was[0][0]=1;
    while(true){
        
        while(!q1.empty()){
            int x=q1.front().f,y=q1.front().s;
            //cout<<x<<" "<<y<<endl;
            q1.pop();
            for(int i=0;i<4;i++){
                int nx=x+dir[i].f,ny=y+dir[i].s;
                if( check(nx,ny) && !was[nx][ny] ){     
                    if(s[x][y]==s[nx][ny])
                        q1.push({nx,ny});
                     else
                        q2.push({nx,ny});             
                    was[nx][ny]=1;
                }
            }
        }
        ans++;
        if(q2.empty())
            break;
        swap(q1,q2);
    }            
    cout<<ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3048 KB Output is correct
2 Correct 3 ms 3048 KB Output is correct
3 Correct 3 ms 3048 KB Output is correct
4 Correct 21 ms 3448 KB Output is correct
5 Correct 8 ms 3448 KB Output is correct
6 Correct 3 ms 3448 KB Output is correct
7 Correct 3 ms 3448 KB Output is correct
8 Correct 4 ms 3448 KB Output is correct
9 Correct 5 ms 3448 KB Output is correct
10 Correct 9 ms 3448 KB Output is correct
11 Correct 10 ms 3448 KB Output is correct
12 Correct 12 ms 3448 KB Output is correct
13 Correct 9 ms 3448 KB Output is correct
14 Correct 9 ms 3448 KB Output is correct
15 Correct 32 ms 4408 KB Output is correct
16 Correct 31 ms 4528 KB Output is correct
17 Correct 32 ms 4892 KB Output is correct
18 Correct 22 ms 4928 KB Output is correct

Subtask #2
63.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 17624 KB Output is correct
2 Correct 121 ms 17624 KB Output is correct
3 Correct 877 ms 65672 KB Output is correct
4 Correct 201 ms 65672 KB Output is correct
5 Correct 542 ms 65672 KB Output is correct
6 Execution timed out 2044 ms 104196 KB Time limit exceeded
7 Correct 28 ms 104196 KB Output is correct
8 Correct 28 ms 104196 KB Output is correct
9 Correct 7 ms 104196 KB Output is correct
10 Correct 6 ms 104196 KB Output is correct
11 Correct 25 ms 104196 KB Output is correct
12 Correct 7 ms 104196 KB Output is correct
13 Correct 136 ms 104196 KB Output is correct
14 Correct 87 ms 104196 KB Output is correct
15 Correct 62 ms 104196 KB Output is correct
16 Correct 52 ms 104196 KB Output is correct
17 Correct 374 ms 104196 KB Output is correct
18 Correct 298 ms 104196 KB Output is correct
19 Correct 211 ms 104196 KB Output is correct
20 Correct 193 ms 104196 KB Output is correct
21 Correct 554 ms 104196 KB Output is correct
22 Correct 509 ms 108300 KB Output is correct
23 Correct 682 ms 112376 KB Output is correct
24 Correct 570 ms 125788 KB Output is correct
25 Correct 991 ms 163292 KB Output is correct
26 Correct 1425 ms 163292 KB Output is correct
27 Correct 1848 ms 192476 KB Output is correct
28 Execution timed out 2065 ms 216636 KB Time limit exceeded
29 Execution timed out 2075 ms 230896 KB Time limit exceeded
30 Correct 1983 ms 244436 KB Output is correct
31 Correct 1374 ms 244436 KB Output is correct
32 Correct 1824 ms 264100 KB Output is correct