oj.uz

Submission #1107888

# Submission time Handle Problem Language Result Execution time Memory
1107888 2024-11-02T09:35:38 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
91.25 / 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];
unordered_map<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[u].pb(v);
                            graph[v].pb(u);
                        }
                    }
                }
 
            }
        }
    }
    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);
    cout.tie(0);

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

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

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 27976 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 11 ms 17908 KB Output is correct
5 Correct 9 ms 13648 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2640 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 4620 KB Output is correct
10 Correct 7 ms 11400 KB Output is correct
11 Correct 4 ms 6752 KB Output is correct
12 Correct 16 ms 14928 KB Output is correct
13 Correct 8 ms 13648 KB Output is correct
14 Correct 8 ms 13648 KB Output is correct
15 Correct 37 ms 29172 KB Output is correct
16 Correct 45 ms 27976 KB Output is correct
17 Correct 37 ms 29472 KB Output is correct
18 Correct 10 ms 17912 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 123640 KB Output is correct
2 Correct 187 ms 112836 KB Output is correct
3 Correct 1213 ms 687604 KB Output is correct
4 Correct 268 ms 158320 KB Output is correct
5 Runtime error 1287 ms 1048576 KB Execution killed with signal 9
6 Correct 1601 ms 239488 KB Output is correct
7 Correct 16 ms 127312 KB Output is correct
8 Correct 16 ms 123520 KB Output is correct
9 Correct 7 ms 4688 KB Output is correct
10 Correct 3 ms 3664 KB Output is correct
11 Correct 14 ms 124496 KB Output is correct
12 Correct 8 ms 11088 KB Output is correct
13 Correct 185 ms 112128 KB Output is correct
14 Correct 116 ms 70844 KB Output is correct
15 Correct 150 ms 92092 KB Output is correct
16 Correct 91 ms 45916 KB Output is correct
17 Correct 582 ms 251840 KB Output is correct
18 Correct 603 ms 291444 KB Output is correct
19 Correct 292 ms 157756 KB Output is correct
20 Correct 301 ms 181108 KB Output is correct
21 Correct 851 ms 433712 KB Output is correct
22 Runtime error 1295 ms 1048576 KB Execution killed with signal 9
23 Correct 989 ms 435976 KB Output is correct
24 Correct 1036 ms 716576 KB Output is correct
25 Runtime error 1585 ms 1048576 KB Execution killed with signal 9
26 Correct 406 ms 123620 KB Output is correct
27 Correct 566 ms 152540 KB Output is correct
28 Correct 1526 ms 239996 KB Output is correct
29 Correct 972 ms 187036 KB Output is correct
30 Correct 808 ms 172748 KB Output is correct
31 Execution timed out 2100 ms 548148 KB Time limit exceeded
32 Correct 694 ms 180628 KB Output is correct