oj.uz

Submission #742285

# Submission time Handle Problem Language Result Execution time Memory
742285 2023-05-16T04:22:05 Z irmuun Tracks in the Snow (BOI13_tracks) C++17
51.875 / 100
 438 ms 1048576 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int h,w;
    cin>>h>>w;
    string s[h+5];
    int used[h+5][w+5];
    for(int i=0;i<h;i++){
        cin>>s[i];
        for(int j=0;j<w;j++){
            used[i][j]=0;
        }
    }
    used[0][0]=1;
    queue<pair<int,int>>q[h*w+5];
    q[1].push({0,0});
    for(int i=1;i<=h*w+1;i++){
        if(q[i].size()==0){
            cout<<i-1;
            return 0;
        }
        while(!q[i].empty()){
            int x=q[i].front().ff,y=q[i].front().ss;
            q[i].pop();
            if(x>0&&used[x-1][y]==0){
                if(s[x-1][y]==s[x][y]){
                    used[x-1][y]=1;
                    q[i].push({x-1,y});
                }
                else if(s[x-1][y]!='.'){
                    used[x-1][y]=1;
                    q[i+1].push({x-1,y});
                }
            }
            if(x<h-1&&used[x+1][y]==0){
                if(s[x+1][y]==s[x][y]){
                    used[x+1][y]=1;
                    q[i].push({x+1,y});
                }
                else if(s[x+1][y]!='.'){
                    used[x+1][y]=1;
                    q[i+1].push({x+1,y});
                }
            }
            if(y>0&&used[x][y-1]==0){
                if(s[x][y-1]==s[x][y]){
                    used[x][y-1]=1;
                    q[i].push({x,y-1});
                }
                else if(s[x][y-1]!='.'){
                    used[x][y-1]=1;
                    q[i+1].push({x,y-1});
                }
            }
            if(y<w-1&&used[x][y+1]==0){
                if(s[x][y+1]==s[x][y]){
                    used[x][y+1]=1;
                    q[i].push({x,y+1});
                }
                else if(s[x][y+1]!='.'){
                    used[x][y+1]=1;
                    q[i+1].push({x,y+1});
                }
            }
        }
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 164048 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 1984 KB Output is correct
4 Correct 81 ms 104748 KB Output is correct
5 Correct 38 ms 57028 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 2004 KB Output is correct
8 Correct 3 ms 3540 KB Output is correct
9 Correct 5 ms 7124 KB Output is correct
10 Correct 32 ms 44376 KB Output is correct
11 Correct 19 ms 27484 KB Output is correct
12 Correct 44 ms 59212 KB Output is correct
13 Correct 41 ms 57044 KB Output is correct
14 Correct 37 ms 57036 KB Output is correct
15 Correct 109 ms 170044 KB Output is correct
16 Correct 124 ms 164144 KB Output is correct
17 Correct 99 ms 161948 KB Output is correct
18 Correct 74 ms 104652 KB Output is correct

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 34132 KB Output is correct
2 Runtime error 430 ms 1048576 KB Execution killed with signal 9
3 Runtime error 425 ms 1048576 KB Execution killed with signal 9
4 Runtime error 420 ms 1048576 KB Execution killed with signal 9
5 Runtime error 413 ms 1048576 KB Execution killed with signal 9
6 Runtime error 401 ms 1048576 KB Execution killed with signal 9
7 Correct 20 ms 30292 KB Output is correct
8 Correct 25 ms 34004 KB Output is correct
9 Correct 26 ms 40092 KB Output is correct
10 Correct 15 ms 22060 KB Output is correct
11 Correct 22 ms 32340 KB Output is correct
12 Correct 10 ms 15572 KB Output is correct
13 Runtime error 412 ms 1048576 KB Execution killed with signal 9
14 Correct 411 ms 611456 KB Output is correct
15 Correct 438 ms 677176 KB Output is correct
16 Correct 297 ms 434436 KB Output is correct
17 Runtime error 404 ms 1048576 KB Execution killed with signal 9
18 Runtime error 418 ms 1048576 KB Execution killed with signal 9
19 Runtime error 433 ms 1048576 KB Execution killed with signal 9
20 Runtime error 426 ms 1048576 KB Execution killed with signal 9
21 Runtime error 393 ms 1048576 KB Execution killed with signal 9
22 Runtime error 435 ms 1048576 KB Execution killed with signal 9
23 Runtime error 400 ms 1048576 KB Execution killed with signal 9
24 Runtime error 422 ms 1048576 KB Execution killed with signal 9
25 Runtime error 394 ms 1048576 KB Execution killed with signal 9
26 Runtime error 386 ms 1048576 KB Execution killed with signal 9
27 Runtime error 402 ms 1048576 KB Execution killed with signal 9
28 Runtime error 380 ms 1048576 KB Execution killed with signal 9
29 Runtime error 395 ms 1048576 KB Execution killed with signal 9
30 Runtime error 397 ms 1048576 KB Execution killed with signal 9
31 Runtime error 388 ms 1048576 KB Execution killed with signal 9
32 Runtime error 400 ms 1048576 KB Execution killed with signal 9