oj.uz

Submission #482520

# Submission time Handle Problem Language Result Execution time Memory
482520 2021-10-25T10:10:45 Z NightRage Tracks in the Snow (BOI13_tracks) C++14
32.1875 / 100
 60 ms 24368 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pb push_back
#define F first
#define S second
#define ii pair<ll,ll>
const long double eps=1e-16;
const ll N = 3e5 + 5, M = 3e5 + 50, LOG = 21, mod = 1000000007, INF = 1e18;
const ld EPS = 1e-16;
ll n,m;



vector<int> adj[N];
int dis[500][500];

string s[500];
bool valid(int i,int j){
    return i>=0 && i<n && j>=0 &&j <m && s[i][j]!='.';
}
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

int main() {
//    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    ll tt = 1;
//    cin >>tt;
    while (tt--) {
        cin >>n >>m;
        for (int i = 0; i < n; ++i) {
            cin >>s[i];
        }

        deque<pair<int,int>>dq;
        dq.push_back({0,0});
        dis[0][0]=1;
        int ans=0;
        while (!dq.empty()){
            auto cur=dq.front();
            dq.pop_front();
            ans=max(ans,dis[cur.first][cur.second]);
            for (int i = 0; i < 4; ++i) {
                int x=cur.first+dx[i],y=cur.second+dy[i];
                if(valid(x,y) && dis[x][y]==0){
                    if(s[x][y]==s[cur.first][cur.second]){
                        dis[x][y]=dis[cur.first][cur.second];
                        dq.push_front({x,y});
                    }else{
                        dis[x][y]=dis[cur.first][cur.second]+1;
                        dq.push_back({x,y});
                    }
                }
            }
        }
        cout << ans <<endl;



    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9072 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 12 ms 8908 KB Output is correct
5 Correct 7 ms 8140 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7496 KB Output is correct
9 Correct 4 ms 7500 KB Output is correct
10 Correct 9 ms 8032 KB Output is correct
11 Correct 7 ms 7852 KB Output is correct
12 Correct 10 ms 8140 KB Output is correct
13 Correct 8 ms 8136 KB Output is correct
14 Correct 9 ms 8140 KB Output is correct
15 Correct 19 ms 9080 KB Output is correct
16 Correct 20 ms 9028 KB Output is correct
17 Correct 14 ms 8908 KB Output is correct
18 Correct 12 ms 8856 KB Output is correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 14732 KB Execution killed with signal 11
2 Runtime error 22 ms 17276 KB Execution killed with signal 11
3 Runtime error 53 ms 24276 KB Execution killed with signal 11
4 Runtime error 32 ms 19524 KB Execution killed with signal 11
5 Runtime error 42 ms 20124 KB Execution killed with signal 11
6 Runtime error 57 ms 24320 KB Execution killed with signal 11
7 Runtime error 11 ms 14796 KB Execution killed with signal 11
8 Runtime error 10 ms 14736 KB Execution killed with signal 11
9 Incorrect 6 ms 7500 KB Output isn't correct
10 Incorrect 5 ms 7360 KB Output isn't correct
11 Runtime error 9 ms 14668 KB Execution killed with signal 11
12 Correct 5 ms 7628 KB Output is correct
13 Runtime error 23 ms 17376 KB Execution killed with signal 11
14 Runtime error 22 ms 17244 KB Execution killed with signal 11
15 Runtime error 21 ms 17232 KB Execution killed with signal 11
16 Incorrect 21 ms 9452 KB Output isn't correct
17 Runtime error 32 ms 19524 KB Execution killed with signal 11
18 Runtime error 35 ms 19524 KB Execution killed with signal 11
19 Runtime error 32 ms 19528 KB Execution killed with signal 11
20 Runtime error 31 ms 19432 KB Execution killed with signal 11
21 Runtime error 40 ms 20128 KB Execution killed with signal 11
22 Runtime error 46 ms 19960 KB Execution killed with signal 11
23 Runtime error 41 ms 19892 KB Execution killed with signal 11
24 Runtime error 44 ms 19872 KB Execution killed with signal 11
25 Runtime error 53 ms 24188 KB Execution killed with signal 11
26 Runtime error 49 ms 20108 KB Execution killed with signal 11
27 Runtime error 56 ms 24132 KB Execution killed with signal 11
28 Runtime error 60 ms 24368 KB Execution killed with signal 11
29 Runtime error 52 ms 24340 KB Execution killed with signal 11
30 Runtime error 52 ms 22340 KB Execution killed with signal 11
31 Runtime error 44 ms 19464 KB Execution killed with signal 11
32 Runtime error 53 ms 22468 KB Execution killed with signal 11