oj.uz

Submission #1107983

# Submission time Handle Problem Language Result Execution time Memory
1107983 2024-11-02T14:11:30 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++11
2.1875 / 100
 1936 ms 811664 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];
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++){
            comp[i][j]=0;
            cin>>arr[i][j];
        }
    }
 
    int x,y;
    int ct=1,a,b,u,v;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j]!='.'){
                if(!comp[i][j]){
                    comp[i][j]= (ct++);
                }
                for(int k=0;k<4;k++){
                    x= i + dx[k];
                    y = j + dy[k];
                    if( x>=0 && y>=0 && x<n && y<m){
                        if(arr[i][j] == arr[x][y]){
                            comp[x][y]=comp[i][j];
                        }
                    }
                }
            }
        }
    }
 
    vector<int> graph[ct+10];
    for( int i=0;i<=ct;i++){
        graph[i]=vector<int>();
    }
    for(int i =0;i<n;i++){
        for(int j=0;j<m;j++){
            if(comp[i][j]!=-1){
 
                for(int x= 0; x<4;x++){
                    a = i + dx[x];
                    b = j + dy[x];
                    if(a>=0 && a<n && b>=0 && b<m && comp[a][b] !=-1 && comp[a][b]!=comp[i][j]){

                        u = min(comp[i][j],comp[a][b]);
                        v =max(comp[i][j],comp[a][b]);
                        // cout<<u<<" "<<v<<endl;
                        graph[u].pb(v);
                        graph[v].pb(u);
                    }
                }
 
            }
        }
    }
    int ans=0;
    queue<pair<int,int>> q;
    vector<int> used(ct,0);
    q.push({1,1});
    used[1]=1;
    while(!q.empty()){
        auto node = q.front();
        ans=max(ans,node.second);
        q.pop();
        for(auto v:graph[node.first]){
            if(!used[v]){
                used[v]=1;
                q.push({v,node.second+1});
            }
        }
    }
    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 37 ms 30916 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 20108 KB Output isn't correct
5 Incorrect 8 ms 12744 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 1 ms 2640 KB Output isn't correct
9 Incorrect 1 ms 4688 KB Output isn't correct
10 Incorrect 7 ms 10952 KB Output isn't correct
11 Incorrect 3 ms 7248 KB Output isn't correct
12 Incorrect 14 ms 15564 KB Output isn't correct
13 Incorrect 8 ms 12744 KB Output isn't correct
14 Incorrect 7 ms 12744 KB Output isn't correct
15 Incorrect 34 ms 30484 KB Output isn't correct
16 Incorrect 46 ms 30924 KB Output isn't correct
17 Incorrect 25 ms 27072 KB Output isn't correct
18 Incorrect 11 ms 20048 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 123080 KB Output isn't correct
2 Incorrect 161 ms 97716 KB Output isn't correct
3 Incorrect 1101 ms 521424 KB Output isn't correct
4 Incorrect 248 ms 128308 KB Output isn't correct
5 Incorrect 1478 ms 811476 KB Output isn't correct
6 Incorrect 1306 ms 495948 KB Output isn't correct
7 Incorrect 19 ms 126924 KB Output isn't correct
8 Incorrect 16 ms 123080 KB Output isn't correct
9 Incorrect 7 ms 4808 KB Output isn't correct
10 Incorrect 3 ms 3276 KB Output isn't correct
11 Incorrect 17 ms 124364 KB Output isn't correct
12 Incorrect 4 ms 8392 KB Output isn't correct
13 Incorrect 188 ms 97700 KB Output isn't correct
14 Incorrect 110 ms 63288 KB Output isn't correct
15 Incorrect 90 ms 72620 KB Output isn't correct
16 Incorrect 73 ms 43108 KB Output isn't correct
17 Incorrect 398 ms 214320 KB Output isn't correct
18 Incorrect 368 ms 215368 KB Output isn't correct
19 Incorrect 258 ms 128416 KB Output isn't correct
20 Incorrect 268 ms 149408 KB Output isn't correct
21 Incorrect 606 ms 335248 KB Output isn't correct
22 Incorrect 1337 ms 811664 KB Output isn't correct
23 Incorrect 771 ms 370280 KB Output isn't correct
24 Incorrect 846 ms 469048 KB Output isn't correct
25 Incorrect 1582 ms 726444 KB Output isn't correct
26 Correct 367 ms 123580 KB Output is correct
27 Incorrect 559 ms 170688 KB Output isn't correct
28 Incorrect 1263 ms 495944 KB Output isn't correct
29 Incorrect 1127 ms 447996 KB Output isn't correct
30 Incorrect 931 ms 375228 KB Output isn't correct
31 Incorrect 1936 ms 693396 KB Output isn't correct
32 Incorrect 646 ms 239268 KB Output isn't correct