oj.uz

Submission #1107902

# Submission time Handle Problem Language Result Execution time Memory
1107902 2024-11-02T09:56:11 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 1461 ms 267608 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5 +5, inf = INT_MAX, LL = 30;

int comp[4005][4005];
int used[4005][4005];
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
void rush(){
    int n,m;
    cin>>n>>m;
 
    vector<vector<char>> arr(n,vector<char>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
            comp[i][j]=-1;
        }
    }
    int ans=0;
    queue<pair<pair<int,int>,int>> q;
    q.push({{0,0},1});
    comp[0][0]=1;
    int cnt=1;
    while(!q.empty()){
        auto node = q.front();
        q.pop();
        if(used[node.first.first][node.first.second]){
            continue;
        }
        ans=max(ans,node.second);
        used[node.first.first][node.first.second]=1;
        for(int i=0;i<4;i++){
            int a = node.first.first + dx[i];
            int b = node.first.second + dy[i];

            if(a>=0 && a<n && b>=0 && b<m){
                if(arr[a][b]!='.'){
                    if(!comp[a][b]){
                        if(arr[a][b]==arr[node.first.first][node.first.second]){
                            comp[a][b]= comp[node.first.first][node.first.second]; 
                        }
                        else{
                            comp[a][b]=++cnt;
                        }
                    }
                    if(comp[a][b]!=comp[node.first.first][node.first.second]){
                        q.push({{a,b}, node.second +1});
                    }
                    else{
                        q.push({{a,b}, node.second});
                    }
                }
                else{
                    q.push({{a,b},node.second});
                }

            }
        }

    }
    putr(ans);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1; 
    // cin>>tt;

    while(tt--){
        rush();
    }

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 20816 KB Output isn't correct
2 Incorrect 1 ms 2384 KB Output isn't correct
3 Incorrect 1 ms 2808 KB Output isn't correct
4 Incorrect 12 ms 20220 KB Output isn't correct
5 Incorrect 7 ms 12636 KB Output isn't correct
6 Incorrect 1 ms 2384 KB Output isn't correct
7 Incorrect 1 ms 2640 KB Output isn't correct
8 Incorrect 2 ms 4704 KB Output isn't correct
9 Incorrect 2 ms 4944 KB Output isn't correct
10 Incorrect 6 ms 10064 KB Output isn't correct
11 Incorrect 4 ms 9808 KB Output isn't correct
12 Incorrect 8 ms 12624 KB Output isn't correct
13 Incorrect 8 ms 12624 KB Output isn't correct
14 Incorrect 7 ms 12624 KB Output isn't correct
15 Incorrect 19 ms 21072 KB Output isn't correct
16 Incorrect 23 ms 20816 KB Output isn't correct
17 Incorrect 18 ms 20968 KB Output isn't correct
18 Incorrect 12 ms 20112 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 137552 KB Output isn't correct
2 Incorrect 131 ms 60360 KB Output isn't correct
3 Incorrect 1461 ms 267592 KB Output isn't correct
4 Incorrect 310 ms 100696 KB Output isn't correct
5 Incorrect 951 ms 186404 KB Output isn't correct
6 Incorrect 1434 ms 267608 KB Output isn't correct
7 Incorrect 25 ms 142408 KB Output isn't correct
8 Incorrect 24 ms 137552 KB Output isn't correct
9 Incorrect 4 ms 2896 KB Output isn't correct
10 Incorrect 3 ms 2808 KB Output isn't correct
11 Incorrect 25 ms 141904 KB Output isn't correct
12 Incorrect 3 ms 7248 KB Output isn't correct
13 Incorrect 109 ms 60320 KB Output isn't correct
14 Incorrect 59 ms 42824 KB Output isn't correct
15 Incorrect 62 ms 46044 KB Output isn't correct
16 Incorrect 38 ms 22096 KB Output isn't correct
17 Incorrect 327 ms 108104 KB Output isn't correct
18 Incorrect 302 ms 107592 KB Output isn't correct
19 Incorrect 304 ms 100680 KB Output isn't correct
20 Incorrect 261 ms 93256 KB Output isn't correct
21 Incorrect 806 ms 193616 KB Output isn't correct
22 Incorrect 741 ms 186356 KB Output isn't correct
23 Incorrect 677 ms 158992 KB Output isn't correct
24 Incorrect 751 ms 191796 KB Output isn't correct
25 Incorrect 1359 ms 267592 KB Output isn't correct
26 Incorrect 1081 ms 233288 KB Output isn't correct
27 Incorrect 1331 ms 267592 KB Output isn't correct
28 Incorrect 1382 ms 267376 KB Output isn't correct
29 Incorrect 1349 ms 267508 KB Output isn't correct
30 Incorrect 1260 ms 262068 KB Output isn't correct
31 Incorrect 846 ms 206424 KB Output isn't correct
32 Incorrect 1365 ms 267552 KB Output isn't correct