oj.uz

Submission #1107899

# Submission time Handle Problem Language Result Execution time Memory
1107899 2024-11-02T09:54:09 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 1430 ms 267628 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});
                    }
                }

            }
        }

    }
    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 2640 KB Output isn't correct
4 Incorrect 11 ms 20300 KB Output isn't correct
5 Incorrect 7 ms 12624 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 4736 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 7 ms 12792 KB Output isn't correct
13 Incorrect 8 ms 12624 KB Output isn't correct
14 Incorrect 7 ms 12464 KB Output isn't correct
15 Incorrect 18 ms 21076 KB Output isn't correct
16 Incorrect 18 ms 20816 KB Output isn't correct
17 Incorrect 16 ms 20816 KB Output isn't correct
18 Incorrect 12 ms 20048 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 137540 KB Output isn't correct
2 Incorrect 119 ms 60232 KB Output isn't correct
3 Incorrect 1430 ms 267456 KB Output isn't correct
4 Incorrect 283 ms 100680 KB Output isn't correct
5 Incorrect 777 ms 186348 KB Output isn't correct
6 Incorrect 1387 ms 267428 KB Output isn't correct
7 Incorrect 30 ms 142408 KB Output isn't correct
8 Incorrect 26 ms 137568 KB Output isn't correct
9 Incorrect 4 ms 2896 KB Output isn't correct
10 Incorrect 2 ms 2640 KB Output isn't correct
11 Incorrect 29 ms 141904 KB Output isn't correct
12 Incorrect 3 ms 7416 KB Output isn't correct
13 Incorrect 108 ms 60232 KB Output isn't correct
14 Incorrect 62 ms 42844 KB Output isn't correct
15 Incorrect 66 ms 46152 KB Output isn't correct
16 Incorrect 48 ms 22088 KB Output isn't correct
17 Incorrect 315 ms 108036 KB Output isn't correct
18 Incorrect 309 ms 107592 KB Output isn't correct
19 Incorrect 330 ms 100680 KB Output isn't correct
20 Incorrect 288 ms 93256 KB Output isn't correct
21 Incorrect 782 ms 193792 KB Output isn't correct
22 Incorrect 705 ms 186384 KB Output isn't correct
23 Incorrect 608 ms 158968 KB Output isn't correct
24 Incorrect 727 ms 191672 KB Output isn't correct
25 Incorrect 1295 ms 267628 KB Output isn't correct
26 Incorrect 1004 ms 233352 KB Output isn't correct
27 Incorrect 1312 ms 267600 KB Output isn't correct
28 Incorrect 1376 ms 267596 KB Output isn't correct
29 Incorrect 1365 ms 267432 KB Output isn't correct
30 Incorrect 1286 ms 262168 KB Output isn't correct
31 Incorrect 849 ms 206480 KB Output isn't correct
32 Incorrect 1327 ms 267592 KB Output isn't correct