oj.uz

Submission #1108073

# Submission time Handle Problem Language Result Execution time Memory
1108073 2024-11-02T16:58:05 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 2000 ms 846156 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++){
            cin>>arr[i][j];
        }
    }
 
    int ct = 0;
    int u,v,a,b;
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         if(arr[i][j]!='.' && comp[i][j]==-1){
    //             queue<pair<int,int>> q;
    //             q.push({i,j});
    //             comp[i][j]=ct;
    //             while(!q.empty()){
 
    //                 pair<int,int> node = q.front();q.pop();
    //                 for(int x=0;x<4;x++){
    //                     a = node.first + dx[x];
    //                     b =  node.second + dy[x];
    //                     if(a>=0 && a<n && b>=0 && b<m && comp[a][b]==-1 && arr[a][b]==arr[i][j]){
    //                         comp[a][b]=ct;
    //                         q.push({a,b});
    //                     }
    //                 }
 
    //             }
    //             ct++;
    //         }
    //     }
    // }
    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 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] && arr[a][b]==arr[i][j]){
                        comp[a][b]=comp[i][j];
                    }
                }
            }
        }
    }
    set<int> graph[ct+11];
    for(int i=0;i<=ct;i++){
        graph[i].clear();
    }
    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]);
                        graph[u].ins(v);
                        graph[v].ins(u);
                    }
                }
 
            }
        }
    }
    int ans=0;
    queue<pair<int,int>> q;
    vector<int> used(ct,0);
    q.push({0,1});
    used[0]=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 64 ms 22088 KB Output isn't correct
2 Incorrect 1 ms 592 KB Output isn't correct
3 Incorrect 1 ms 592 KB Output isn't correct
4 Incorrect 15 ms 5456 KB Output isn't correct
5 Incorrect 12 ms 4688 KB Output isn't correct
6 Incorrect 1 ms 336 KB Output isn't correct
7 Incorrect 1 ms 592 KB Output isn't correct
8 Incorrect 2 ms 848 KB Output isn't correct
9 Incorrect 2 ms 1116 KB Output isn't correct
10 Incorrect 11 ms 4384 KB Output isn't correct
11 Incorrect 5 ms 1872 KB Output isn't correct
12 Incorrect 23 ms 8440 KB Output isn't correct
13 Incorrect 13 ms 4688 KB Output isn't correct
14 Incorrect 12 ms 4856 KB Output isn't correct
15 Incorrect 69 ms 19784 KB Output isn't correct
16 Incorrect 64 ms 21968 KB Output isn't correct
17 Incorrect 54 ms 16796 KB Output isn't correct
18 Incorrect 15 ms 5456 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 17744 KB Output isn't correct
2 Incorrect 281 ms 82508 KB Output isn't correct
3 Incorrect 1980 ms 522080 KB Output isn't correct
4 Incorrect 483 ms 114504 KB Output isn't correct
5 Execution timed out 2109 ms 846156 KB Time limit exceeded
6 Incorrect 1968 ms 383000 KB Output isn't correct
7 Incorrect 16 ms 18256 KB Output isn't correct
8 Incorrect 17 ms 17744 KB Output isn't correct
9 Incorrect 9 ms 3152 KB Output isn't correct
10 Incorrect 3 ms 1104 KB Output isn't correct
11 Incorrect 14 ms 17232 KB Output isn't correct
12 Incorrect 8 ms 3920 KB Output isn't correct
13 Incorrect 280 ms 81904 KB Output isn't correct
14 Incorrect 156 ms 48712 KB Output isn't correct
15 Incorrect 160 ms 51016 KB Output isn't correct
16 Incorrect 124 ms 40264 KB Output isn't correct
17 Incorrect 706 ms 204768 KB Output isn't correct
18 Incorrect 742 ms 188148 KB Output isn't correct
19 Incorrect 447 ms 116488 KB Output isn't correct
20 Incorrect 467 ms 126792 KB Output isn't correct
21 Incorrect 1288 ms 321108 KB Output isn't correct
22 Execution timed out 2078 ms 836404 KB Time limit exceeded
23 Incorrect 1547 ms 395656 KB Output isn't correct
24 Incorrect 1644 ms 441268 KB Output isn't correct
25 Execution timed out 2076 ms 619180 KB Time limit exceeded
26 Correct 388 ms 129020 KB Output is correct
27 Incorrect 560 ms 155360 KB Output isn't correct
28 Incorrect 1913 ms 381348 KB Output isn't correct
29 Incorrect 1583 ms 313672 KB Output isn't correct
30 Incorrect 1291 ms 245724 KB Output isn't correct
31 Execution timed out 2126 ms 831580 KB Time limit exceeded
32 Incorrect 757 ms 187000 KB Output isn't correct