oj.uz

Submission #1107884

# Submission time Handle Problem Language Result Execution time Memory
1107884 2024-11-02T09:27:52 Z 0pt1mus23 Tracks in the Snow (BOI13_tracks) C++14
21.5625 / 100
 823 ms 295692 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];
int edg[4005][4005];
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;
    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++){
                        int a = node.first + dx[x];
                        int 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++;
            }
 
        }
    }  
    assert(ct<4005);
 
    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++){
                    int a = i + dx[x];
                    int b = j + dy[x];
                    if(a>=0 && a<n && b>=0 && b<m && comp[a][b] !=-1 && comp[a][b]!=comp[i][j]){
                        if(edg[comp[i][j]][comp[a][b]]==0 ){
                            edg[comp[i][j]][comp[a][b]]=1;
                            graph[comp[i][j]].pb(comp[a][b]);
                        }
                    }
                }
 
            }
        }
    }
    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);

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

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

    return 0;
}

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 34652 KB Execution killed with signal 6
2 Correct 1 ms 3152 KB Output is correct
3 Correct 2 ms 3920 KB Output is correct
4 Correct 18 ms 30524 KB Output is correct
5 Runtime error 31 ms 21492 KB Execution killed with signal 6
6 Correct 1 ms 3152 KB Output is correct
7 Correct 2 ms 3920 KB Output is correct
8 Correct 3 ms 5624 KB Output is correct
9 Correct 3 ms 7068 KB Output is correct
10 Runtime error 25 ms 17384 KB Execution killed with signal 6
11 Correct 6 ms 12624 KB Output is correct
12 Runtime error 29 ms 21552 KB Execution killed with signal 6
13 Runtime error 27 ms 21584 KB Execution killed with signal 6
14 Runtime error 27 ms 21584 KB Execution killed with signal 6
15 Runtime error 44 ms 34636 KB Execution killed with signal 6
16 Runtime error 45 ms 34644 KB Execution killed with signal 6
17 Runtime error 43 ms 34648 KB Execution killed with signal 6
18 Correct 18 ms 30544 KB Output is correct

Subtask #2
6.5625 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 162 ms 246564 KB Execution killed with signal 6
2 Runtime error 101 ms 87880 KB Execution killed with signal 6
3 Runtime error 455 ms 295692 KB Execution killed with signal 6
4 Runtime error 177 ms 130888 KB Execution killed with signal 6
5 Runtime error 387 ms 214600 KB Execution killed with signal 6
6 Runtime error 805 ms 287304 KB Execution killed with signal 6
7 Runtime error 186 ms 254792 KB Execution killed with signal 6
8 Runtime error 179 ms 246344 KB Execution killed with signal 6
9 Runtime error 17 ms 4944 KB Execution killed with signal 6
10 Correct 10 ms 12892 KB Output is correct
11 Correct 20 ms 134480 KB Output is correct
12 Runtime error 21 ms 13312 KB Execution killed with signal 6
13 Runtime error 107 ms 86860 KB Execution killed with signal 6
14 Runtime error 79 ms 64764 KB Execution killed with signal 6
15 Runtime error 81 ms 69116 KB Execution killed with signal 6
16 Runtime error 58 ms 31048 KB Execution killed with signal 6
17 Runtime error 206 ms 137800 KB Execution killed with signal 6
18 Runtime error 213 ms 137544 KB Execution killed with signal 6
19 Runtime error 170 ms 128840 KB Execution killed with signal 6
20 Runtime error 146 ms 119880 KB Execution killed with signal 6
21 Runtime error 318 ms 218952 KB Execution killed with signal 6
22 Runtime error 432 ms 210124 KB Execution killed with signal 6
23 Runtime error 342 ms 178504 KB Execution killed with signal 6
24 Runtime error 348 ms 218440 KB Execution killed with signal 6
25 Runtime error 644 ms 287288 KB Execution killed with signal 6
26 Correct 415 ms 123468 KB Output is correct
27 Runtime error 739 ms 287352 KB Execution killed with signal 6
28 Runtime error 823 ms 287304 KB Execution killed with signal 6
29 Runtime error 805 ms 287304 KB Execution killed with signal 6
30 Runtime error 741 ms 281688 KB Execution killed with signal 6
31 Runtime error 676 ms 229016 KB Execution killed with signal 6
32 Runtime error 596 ms 287304 KB Execution killed with signal 6