oj.uz

Submission #1107971

# Submission time Handle Problem Language Result Execution time Memory
1107971 2024-11-02T13:32:21 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++11
91.25 / 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+5);
    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]);
                        // assert(v<ct);
                        if(v>=ct){
                            while(true){
                                
                            }
                        }
                        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 50 ms 25416 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 10 ms 17612 KB Output is correct
5 Correct 9 ms 12624 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 2 ms 4688 KB Output is correct
10 Correct 8 ms 10576 KB Output is correct
11 Correct 4 ms 6736 KB Output is correct
12 Correct 14 ms 13904 KB Output is correct
13 Correct 8 ms 12624 KB Output is correct
14 Correct 10 ms 12788 KB Output is correct
15 Correct 34 ms 25932 KB Output is correct
16 Correct 38 ms 25424 KB Output is correct
17 Correct 30 ms 25808 KB Output is correct
18 Correct 10 ms 17488 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 122960 KB Output is correct
2 Correct 152 ms 92488 KB Output is correct
3 Correct 1083 ms 504728 KB Output is correct
4 Correct 239 ms 127304 KB Output is correct
5 Runtime error 1525 ms 1048576 KB Execution killed with signal 9
6 Correct 1173 ms 242716 KB Output is correct
7 Correct 16 ms 126800 KB Output is correct
8 Correct 16 ms 122960 KB Output is correct
9 Correct 6 ms 4176 KB Output is correct
10 Correct 3 ms 3268 KB Output is correct
11 Correct 14 ms 124324 KB Output is correct
12 Correct 7 ms 9296 KB Output is correct
13 Correct 169 ms 92048 KB Output is correct
14 Correct 95 ms 58564 KB Output is correct
15 Correct 137 ms 70936 KB Output is correct
16 Correct 67 ms 37832 KB Output is correct
17 Correct 402 ms 195592 KB Output is correct
18 Correct 563 ms 210996 KB Output is correct
19 Correct 242 ms 127200 KB Output is correct
20 Correct 292 ms 142448 KB Output is correct
21 Correct 629 ms 330712 KB Output is correct
22 Runtime error 1667 ms 1048576 KB Execution killed with signal 9
23 Correct 760 ms 332528 KB Output is correct
24 Correct 838 ms 494408 KB Output is correct
25 Execution timed out 2097 ms 729952 KB Time limit exceeded
26 Correct 400 ms 123428 KB Output is correct
27 Correct 626 ms 144724 KB Output is correct
28 Correct 1167 ms 242704 KB Output is correct
29 Correct 1035 ms 199984 KB Output is correct
30 Correct 840 ms 181040 KB Output is correct
31 Execution timed out 2075 ms 453320 KB Time limit exceeded
32 Correct 559 ms 172084 KB Output is correct