oj.uz

Submission #1107886

# Submission time Handle Problem Language Result Execution time Memory
1107886 2024-11-02T09:33:50 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
6.04167 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
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];
gp_hash_table<int,gp_hash_table<int,int>> edg;
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]=-1;
            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++;
            }
 
        }
    }
    vector<int> graph[ct];
    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]);
                        if(edg[u][v]==0 ){
                            edg[u][v]=1;
                            graph[comp[i][j]].pb(comp[a][b]);
                        }
                    }
                }
 
            }
        }
    }
    edg.clear();
    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);

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

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

    return 0;
}

Subtask #1
1.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 40488 KB Output isn't correct
2 Incorrect 1 ms 2640 KB Output isn't correct
3 Incorrect 1 ms 2640 KB Output isn't correct
4 Incorrect 11 ms 17744 KB Output isn't correct
5 Incorrect 12 ms 15796 KB Output isn't correct
6 Incorrect 1 ms 2640 KB Output isn't correct
7 Incorrect 1 ms 2640 KB Output isn't correct
8 Incorrect 2 ms 2384 KB Output isn't correct
9 Incorrect 2 ms 4944 KB Output isn't correct
10 Incorrect 11 ms 13688 KB Output isn't correct
11 Correct 4 ms 6736 KB Output is correct
12 Incorrect 18 ms 16504 KB Output isn't correct
13 Incorrect 12 ms 15796 KB Output isn't correct
14 Incorrect 15 ms 15796 KB Output isn't correct
15 Incorrect 48 ms 38440 KB Output isn't correct
16 Incorrect 52 ms 40488 KB Output isn't correct
17 Incorrect 40 ms 37788 KB Output isn't correct
18 Incorrect 11 ms 17744 KB Output isn't correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 126584 KB Output isn't correct
2 Incorrect 228 ms 203016 KB Output isn't correct
3 Runtime error 1286 ms 1048576 KB Execution killed with signal 9
4 Incorrect 298 ms 223808 KB Output isn't correct
5 Runtime error 1157 ms 1048576 KB Execution killed with signal 9
6 Incorrect 1559 ms 268560 KB Output isn't correct
7 Incorrect 17 ms 128348 KB Output isn't correct
8 Incorrect 19 ms 126584 KB Output isn't correct
9 Incorrect 10 ms 7812 KB Output isn't correct
10 Incorrect 4 ms 4956 KB Output isn't correct
11 Incorrect 16 ms 126044 KB Output isn't correct
12 Incorrect 12 ms 16308 KB Output isn't correct
13 Incorrect 223 ms 203432 KB Output isn't correct
14 Incorrect 121 ms 110620 KB Output isn't correct
15 Incorrect 193 ms 188424 KB Output isn't correct
16 Incorrect 93 ms 58624 KB Output isn't correct
17 Incorrect 673 ms 390968 KB Output isn't correct
18 Incorrect 933 ms 684792 KB Output isn't correct
19 Incorrect 321 ms 224520 KB Output isn't correct
20 Incorrect 427 ms 373220 KB Output isn't correct
21 Incorrect 1101 ms 742416 KB Output isn't correct
22 Runtime error 1185 ms 1048576 KB Execution killed with signal 9
23 Incorrect 1196 ms 726092 KB Output isn't correct
24 Runtime error 1138 ms 1048576 KB Execution killed with signal 9
25 Runtime error 1464 ms 1048576 KB Execution killed with signal 9
26 Correct 460 ms 123624 KB Output is correct
27 Correct 600 ms 144144 KB Output is correct
28 Incorrect 1576 ms 252960 KB Output isn't correct
29 Incorrect 1036 ms 186420 KB Output isn't correct
30 Incorrect 813 ms 184700 KB Output isn't correct
31 Execution timed out 2110 ms 868956 KB Time limit exceeded
32 Incorrect 579 ms 224092 KB Output isn't correct