oj.uz

Submission #1107891

# Submission time Handle Problem Language Result Execution time Memory
1107891 2024-11-02T09:41:18 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
91.25 / 100
 2000 ms 778960 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;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
int comp[4005][4005];
unordered_map<int,unordered_map<int,int>,custom_hash   > 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);
                        }
                    }
                }
 
            }
        }
    }
    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 49 ms 25672 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 12 ms 17628 KB Output is correct
5 Correct 10 ms 13136 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 4688 KB Output is correct
10 Correct 10 ms 10968 KB Output is correct
11 Correct 4 ms 6736 KB Output is correct
12 Correct 16 ms 14004 KB Output is correct
13 Correct 9 ms 13136 KB Output is correct
14 Correct 8 ms 13136 KB Output is correct
15 Correct 38 ms 26740 KB Output is correct
16 Correct 42 ms 25672 KB Output is correct
17 Correct 36 ms 27004 KB Output is correct
18 Correct 12 ms 17488 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 123216 KB Output is correct
2 Correct 264 ms 96764 KB Output is correct
3 Correct 1937 ms 565140 KB Output is correct
4 Correct 446 ms 136892 KB Output is correct
5 Execution timed out 2070 ms 762048 KB Time limit exceeded
6 Correct 1225 ms 228328 KB Output is correct
7 Correct 16 ms 126960 KB Output is correct
8 Correct 17 ms 123276 KB Output is correct
9 Correct 7 ms 4432 KB Output is correct
10 Correct 3 ms 3408 KB Output is correct
11 Correct 14 ms 124496 KB Output is correct
12 Correct 9 ms 10020 KB Output is correct
13 Correct 210 ms 97468 KB Output is correct
14 Correct 134 ms 62652 KB Output is correct
15 Correct 181 ms 78780 KB Output is correct
16 Correct 102 ms 39764 KB Output is correct
17 Correct 663 ms 214524 KB Output is correct
18 Correct 799 ms 241404 KB Output is correct
19 Correct 360 ms 139112 KB Output is correct
20 Correct 383 ms 155448 KB Output is correct
21 Correct 1323 ms 366636 KB Output is correct
22 Execution timed out 2088 ms 726660 KB Time limit exceeded
23 Correct 1473 ms 371696 KB Output is correct
24 Correct 1868 ms 584912 KB Output is correct
25 Execution timed out 2107 ms 778960 KB Time limit exceeded
26 Correct 401 ms 131656 KB Output is correct
27 Correct 586 ms 155560 KB Output is correct
28 Correct 1260 ms 230180 KB Output is correct
29 Correct 1074 ms 199236 KB Output is correct
30 Correct 922 ms 184624 KB Output is correct
31 Execution timed out 2083 ms 467564 KB Time limit exceeded
32 Correct 603 ms 186020 KB Output is correct