oj.uz

Submission #1107970

# Submission time Handle Problem Language Result Execution time Memory
1107970 2024-11-02T13:30:33 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++11
93.4375 / 100
 2000 ms 1048576 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];
vector<unordered_map<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++;
            }
        }
    }
    edg.resize(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 38 ms 25536 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 11 ms 17488 KB Output is correct
5 Correct 8 ms 12624 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Correct 1 ms 4688 KB Output is correct
10 Correct 8 ms 10576 KB Output is correct
11 Correct 4 ms 6696 KB Output is correct
12 Correct 14 ms 13904 KB Output is correct
13 Correct 10 ms 12624 KB Output is correct
14 Correct 8 ms 12624 KB Output is correct
15 Correct 36 ms 25936 KB Output is correct
16 Correct 37 ms 25416 KB Output is correct
17 Correct 31 ms 25840 KB Output is correct
18 Correct 11 ms 17488 KB Output is correct

Subtask #2
63.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 122960 KB Output is correct
2 Correct 184 ms 91464 KB Output is correct
3 Correct 900 ms 504712 KB Output is correct
4 Correct 232 ms 126792 KB Output is correct
5 Runtime error 1756 ms 1048576 KB Execution killed with signal 9
6 Correct 1070 ms 242748 KB Output is correct
7 Correct 15 ms 126800 KB Output is correct
8 Correct 16 ms 122960 KB Output is correct
9 Correct 7 ms 4176 KB Output is correct
10 Correct 3 ms 3152 KB Output is correct
11 Correct 15 ms 124240 KB Output is correct
12 Correct 8 ms 9464 KB Output is correct
13 Correct 185 ms 91676 KB Output is correct
14 Correct 82 ms 58340 KB Output is correct
15 Correct 134 ms 70952 KB Output is correct
16 Correct 73 ms 37252 KB Output is correct
17 Correct 383 ms 195360 KB Output is correct
18 Correct 506 ms 211528 KB Output is correct
19 Correct 241 ms 126792 KB Output is correct
20 Correct 215 ms 141396 KB Output is correct
21 Correct 583 ms 325340 KB Output is correct
22 Runtime error 1822 ms 1048576 KB Execution killed with signal 9
23 Correct 686 ms 332620 KB Output is correct
24 Correct 696 ms 500340 KB Output is correct
25 Execution timed out 2062 ms 736012 KB Time limit exceeded
26 Correct 392 ms 126280 KB Output is correct
27 Correct 552 ms 144648 KB Output is correct
28 Correct 1109 ms 244020 KB Output is correct
29 Correct 999 ms 200108 KB Output is correct
30 Correct 885 ms 181040 KB Output is correct
31 Correct 1920 ms 453448 KB Output is correct
32 Correct 563 ms 176724 KB Output is correct