oj.uz

Submission #1107890

# Submission time Handle Problem Language Result Execution time Memory
1107890 2024-11-02T09:40:00 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
39.1667 / 100
 1237 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;


int comp[4005][4005];
unordered_map<int,vector<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++;
            }
 
        }
    }
    for(int i=0;i<ct;i++){
        edg[i].resize(ct,0);
    }
    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
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 701 ms 1048576 KB Execution killed with signal 9
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 60 ms 90440 KB Output is correct
5 Correct 311 ms 470316 KB Output is correct
6 Correct 1 ms 2640 KB Output is correct
7 Correct 2 ms 3408 KB Output is correct
8 Correct 2 ms 2896 KB Output is correct
9 Correct 3 ms 7248 KB Output is correct
10 Correct 319 ms 498516 KB Output is correct
11 Correct 9 ms 13392 KB Output is correct
12 Runtime error 693 ms 1048576 KB Execution killed with signal 9
13 Correct 316 ms 470504 KB Output is correct
14 Correct 321 ms 470600 KB Output is correct
15 Runtime error 678 ms 1048576 KB Execution killed with signal 9
16 Runtime error 627 ms 1048576 KB Execution killed with signal 9
17 Runtime error 640 ms 1048576 KB Execution killed with signal 9
18 Correct 53 ms 90440 KB Output is correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 326164 KB Output is correct
2 Runtime error 655 ms 1048576 KB Execution killed with signal 9
3 Runtime error 793 ms 1048576 KB Execution killed with signal 9
4 Runtime error 768 ms 1048576 KB Execution killed with signal 9
5 Runtime error 796 ms 1048576 KB Execution killed with signal 9
6 Runtime error 1229 ms 1048576 KB Execution killed with signal 9
7 Correct 119 ms 278600 KB Output is correct
8 Correct 154 ms 325960 KB Output is correct
9 Correct 208 ms 314952 KB Output is correct
10 Correct 33 ms 53576 KB Output is correct
11 Correct 40 ms 159568 KB Output is correct
12 Correct 624 ms 953416 KB Output is correct
13 Runtime error 710 ms 1048576 KB Execution killed with signal 9
14 Runtime error 668 ms 1048576 KB Execution killed with signal 9
15 Runtime error 682 ms 1048576 KB Execution killed with signal 9
16 Runtime error 697 ms 1048576 KB Execution killed with signal 9
17 Runtime error 609 ms 1048576 KB Execution killed with signal 9
18 Runtime error 587 ms 1048576 KB Execution killed with signal 9
19 Runtime error 687 ms 1048576 KB Execution killed with signal 9
20 Runtime error 510 ms 1048576 KB Execution killed with signal 9
21 Runtime error 602 ms 1048576 KB Execution killed with signal 9
22 Runtime error 689 ms 1048576 KB Execution killed with signal 9
23 Runtime error 667 ms 1048576 KB Execution killed with signal 9
24 Runtime error 689 ms 1048576 KB Execution killed with signal 9
25 Runtime error 957 ms 1048576 KB Execution killed with signal 9
26 Correct 414 ms 134096 KB Output is correct
27 Runtime error 1083 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1175 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1210 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1237 ms 1048576 KB Execution killed with signal 9
31 Runtime error 1026 ms 1048576 KB Execution killed with signal 9
32 Runtime error 946 ms 1048576 KB Execution killed with signal 9